# Tag Info

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,140
Accepted

• 15.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 ...
• 18.1k
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.4k
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 ...
• 27k
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,305

### 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,156

### 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,643

• 5,742

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

Müller and Szeider study Resolution proofs where the proof DAG has bounded tree-width or bounded path-width (for suitable extensions of these graph complexity measures to directed graphs.) They show ...
• 4,511

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

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

More generally, if we can pick any problem in NP−P, and use an oracle for it, then which of the problems in P could see a speed-up? This question gets more directly at representation and time ...
• 7,140
Accepted

### Is there a simple game with asymmetric complexity?

Perhaps a fairly natural game is the following: Player 1 is placed in the middle of a maze and must reach the exit in order to win. Player 2 is in the same maze and must collect a set of "components"...
• 22.4k