搜索结果: 1-6 共查到“数学 P = NP”相关记录6条 . 查询时间(0.082 秒)
研究两类广义控制问题的复杂性: k-步长控制问题和k-距离控制问题, 证明了k-步长控制问题在弦图和平面二部图上都是NP-完全的. 作为上述结果的推论, 给出了k-距离控制问题在弦图和二部图上NP-完全性的新的证明, 并进一步证明了k-距离控制问题在平面二部图上也是NP-完全的.
NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems
NP-hardness of Deciding Convexity of Quartic Polynomials Related Problems
2011/1/19
We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time)
algorithm that can decide whether a multivariate polynomial of degree four (or higher even
degree) is globa...
Low-Rank Matrix Approximation with Weights or Missing Data is NP-hard
low-rank matrix approximation weighted low-rank approximation missing data
2011/1/17
Weighted low-rank approximation (WLRA), a dimensionality reduction technique for data anal-
ysis, has been successfully used in several applications, such as in collaborative filtering to design reco...
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...
I prove that if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be v...
NP图灵完全集;性质
NP图灵完全集的一些性质
2007/12/10
本文主要结果是:(1)P=NP 当且仅当一切 NP 图灵完全的无穷集组成一个非递归可表现的类;(2)NP=co-NP 当且仅当一切 NP 图灵完全集恰好组成一个多项式时间图灵等价类;(3)NP=co-NP 当且仅当$NP=P^{SAT}$.