# Tag Info

Accepted

### 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$) ...
• 17.4k
Accepted

### What is the 'P=NP?' building?

The building in question is the Princeton CS building: https://www.cs.princeton.edu/general/bricks Here is a photo of the bricks:
• 883

### 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 ...
• 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 ...
• 384
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 ...
• 10.8k

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