搜索结果: 1-6 共查到“理学 computational complexity”相关记录6条 . 查询时间(0.096 秒)
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...