# Tag Info

## Hot answers tagged np

Accepted

### Is there an NP-complete language that contains precisely half of the n-bit instances?

I asked this question a few years ago and Boaz Barak positively answered it. The statement is equivalent to the existence of an NP-complete language $L$ where $|L_n|$ is polynomial-time computable. ...
• 1,781
Accepted

### Implications of proving NP=RP on complexity theory

Prelude: the below is just one consequence of $\mathsf{RP}=\mathsf{NP}$ and probably not the most important, e.g. compared to collapse of the polynomial hierarchy. There was a great and more ...
• 7,052

### Graph theoretic restriction to Proofs in Proof Complexity Theory

The most natural restriction on the proof DAG is that it be a tree – that is, any "lemma" (intermediate conclusion) is not used more than once. This property is called being "tree-like". General ...
• 14.1k
Accepted

• 22.3k
Accepted

### Euclidean TSP in NP and square root complexity

Q1. This is a notorious open problem. It is known to be in the fourth level of the counting hierarchy, due to [ABKM]. Not known to be in NP. The problem is not really in computing square roots as ...
Accepted

### Algorithm whose running time depends on P vs. NP

If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following: ...
• 22.3k
Accepted

### (How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

You may wish to look at cost semantics for functional languages. These are various computational complexity measures for functional languages that do not pass through any kind of Turing machine, RAM ...
• 26.6k

### Integer linear programming in logarithmic number of variables

I can only give a partial answer to this question. A result by Lenstra (later improved by Kannan, and Frank and Tardos) states that ILP with $k$ variables can be solved in time $k^{O(k)}$ (times a ...
• 3,094
Accepted

### How much would a SAT oracle help speeding up polynomial time algorithms?

Actually, acceptance of nondeterministic Turing machines in time $t$ is $O(t \log t)$-time reducible to SAT (the construction is via oblivious simulation, see Arora-Barak), so typically any time a ...
• 2,295

### Questions regarding SETH

The subtlety comes in where we introduce the notion of "harder". The reduction showing that SAT can be reduced to Hamiltonian Cycle shows that the latter is "harder" up to polynomial factors. In doing ...
• 1,624

• 5,712

### Is there an NP-complete language that contains precisely half of the n-bit instances?

Here's a suggestion of why it might be difficult to come up with an example of such, though I agree with Kaveh's comment that it would be surprising if it didn't exist. [Not an answer, but too long ...
• 35.7k
Accepted

### List of NP-Complete graph problems/ properties?

A general list of NP-complete problems can be found in Garey & Johnson's book "Computers and Intractability". It contains an appendix that lists roughly 300 NP-complete problems, and despite its ...
• 778