Skip to main content
13 votes

Formulating P vs NP without Turing machines

$\def\cat{_\smile}$Sure. By a classical result of Cobham, the set FP of polynomial-time functions can be described as the smallest set of functions $f\colon(\{0,1\}^*)^n\to\{0,1\}^*$ ($n\in\mathbb N$) ...
Emil Jeřábek's user avatar
3 votes

What is the 'P=NP?' building?

The building in question is the Princeton CS building: Here is a photo of the bricks:
Wei Zhan's user avatar
  • 883
2 votes

Formulating P vs NP without Turing machines

In Descriptive Complexity, consider the logical language consisting of two sorts: unary numbers $x$ and binary string $Y$, and $\{0,1,+,*, \leq, =\}$ on unary numbers (commutative discrete ordered ...
Kaveh's user avatar
  • 21.6k
1 vote

Bottom up TSP solution?

"If one takes the 2 nearest neighbors of every node and adds them all up, that is a theoretical minimum." This isn't true. You are adding up 2 edges per vertex, where a TSP solution has one ...
NaturalLogZ's user avatar
1 vote

Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?

Finding the factorization of a single-variable polynomial with rational coefficients is apparently solvable in poly time, as shown in [1]: [1] Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. Factoring ...
Neal Young's user avatar
  • 10.8k

Only top scored, non community-wiki answers of a minimum length are eligible