搜索结果: 1-13 共查到“Computational Complexity”相关记录13条 . 查询时间(0.125 秒)
Measuring Empirical Computational Complexity
trend-prof empirical computational complexity
2016/5/24
The standard language for describing the asymptotic behavior of algorithms is theoretical computational complexity. We propose a method for describing the asymptotic behavior of programs in practice b...
Pattern perception and computational complexity: introduction to the special issue
comparative cognition brain imaging pattern perception artificial grammar learning formal language theory theory of computation
2015/4/20
Research on pattern perception and rule learning, grounded in formal language theory (FLT) and using artificial grammar learning paradigms, has exploded in the last decade. This approach marries empir...
Computational Complexity of Arbitrage in Frictional Security Market
arbitrage condition financial market complexity of arbitrage
2011/9/17
We are interested in computation of arbitrage condition in financial market with friction. We consider a deterministic model with a finite number of financial assets and a finite number of possible st...
A Computational Complexity-Theoretic Elaboration of Weak Truth-Table Reducibility
algorithmic information theory algorithmic randomness weak truth-table reducibility
2011/9/14
Abstract: The notion of weak truth-table reducibility plays an important role in recursion theory. In this paper, we introduce an elaboration of this notion, where a computable bound on the use functi...
On the computational complexity of stochastic controller optimization in POMDPs
Partially observable Markov decision process stochastic controller bilinear program computational complexity Motzkin-Straus theorem
2011/10/8
Abstract: We show that the problem of finding an optimal stochastic 'blind' controller in a Markov decision process is an NP-hard problem. The corresponding decision problem is NP-hard, in PSPACE, and...
The computational complexity of recognising embeddings in finitely presented groups
Finitely presented groups embeddings Kleene’s arithmetical hierarchy decidability universal finitely presented group
2011/8/29
Abstract: We extend a result by Lempp that recognising torsion-freeness for finitely presented groups is $\Pi^{0}_{2}$-complete; we show that the problem of recognising embeddings of finitely presente...
Duality Gap, Computational Complexity and NP Completeness: A Survey
Duality Gap Computational Complexity NP Completeness
2011/2/28
In this paper, we survey research that studies the connection between the computational complexity of optimization problems on the one hand, and the duality gap between the primal and dual optimizatio...
Why Philosophers Should Care About Computational Complexity
quantum computing omniscience bounded rationality PAC-learning computationalism
2011/9/7
One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed c...
Statistical mechanics of classical and quantum computational complexity
Statistical mechanics classical quantum computational
2010/10/22
The quest for quantum computers is motivated by their potential for solving problems that defy
existing, classical, computers. The theory of computational complexity, one of the crown jewels of compu...
Errors in Computational Complexity Proofs for Protocols
Computational Complexity Proofs security properties of protocols assuring protocol
2009/3/9
Proofs are invaluable tools in assuring protocol implementers
about the security properties of protocols. However, several instances of
undetected aws in the proofs of protocols (resulting in awed p...
Constant Round Group Key Exchange with Logarithmic Computational Complexity
Group key exchange scalability binary tree provable security
2008/12/15
Protocols for group key exchange (GKE) are cryptographic algorithms that describe
how a group of parties communicating over a public network can come up with a common secret key.Due to their critical...
On the Computational Complexity of MCMC-based Estimators in Large Samples
Markov Chain Monte Carlo Computational Complexity Bayesian Increasing Dimension
2010/4/28
In this paper we examine the implications of the statistical large
sample theory for the computational complexity of Bayesian and quasi-
Bayesian estimation carried out using Metropolis random walks...
This is the home page of the Colloquium of Computational Complexity (ECCC). The document contains full text fragments from monographs and lecture notes. It is being continously upgraded. There are rel...