Hot answers tagged

24 votes
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. ...
user avatar
22 votes
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 ...
user avatar
  • 7,052
19 votes

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 ...
user avatar
  • 14.1k
19 votes
Accepted

If BQP contains NP, does this mean that P=NP?

No, $\mathrm{NP}\subseteq\mathrm{BQP}$ is not known to imply $\mathrm P=\mathrm{NP}$. Even the stronger assumption $\mathrm{NP}\subseteq\mathrm{BPP}$ is not known to yield a deeper collapse than $\...
user avatar
19 votes
Accepted

Intersection of languages in NP

Just an extended comment to better explain ARi's comment (I was writing it while I saw it). It is sufficient to use a "large gap" approach similar to the one used in Lardner's theorem; for example: $...
user avatar
19 votes
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 ...
user avatar
17 votes
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: ...
user avatar
16 votes
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 ...
user avatar
  • 26.6k
15 votes

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 ...
user avatar
15 votes
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 ...
user avatar
  • 2,295
14 votes

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 ...
user avatar
  • 1,624
14 votes

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

At the request of Andrej and PhD, I am turning my comment into an answer, with apologies for self-advertising. I recently wrote a paper in which I look at how to prove the Cook-Levin theorem ($\...
user avatar
14 votes
Accepted

When was co-NP introduced for the first time?

Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper "the equivalence problem for regular expressions with squaring requires exponential space"...
user avatar
12 votes
Accepted

Are There Highly Symmetric NP- or P-complete Languages?

For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-...
user avatar
11 votes
Accepted

$NP$-complete problem with quasi-polynomial bound on the number of solutions

This is a very interesting question. First, a clarifying remark. Note that "upper bound on the number of witnesses" is not a property of a computational problem per se, but of a particular verifier ...
user avatar
11 votes

Are there knot theoretic formulations of NP complete problems?

You can take a look to: Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac, and Aleksandar Chakarov. 2009. Tricolorable torus knots are NP-complete. In Proceedings of the 47th Annual ...
user avatar
11 votes
Accepted

Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below). We want ...
user avatar
11 votes

"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = ...
user avatar
10 votes

Natural NP-complete problems with "large" witnesses

How about the edge coloring number in a dense graph (aka Chromatic index)? You are given the adjacency matrix of an $n$ vertex graph ($n^2$ bit input), but the natural witness describing the coloring ...
user avatar
9 votes

Are there knot theoretic formulations of NP complete problems?

There are a few references in the first paragraph of Marc Lackenby. A polynomial upper bound on Reidemeister moves. arXiv:1302.0180 In particular, the author says that the problem of recognizing ...
user avatar
8 votes

Natural NP-complete problems with "large" witnesses

Here is an example, which appears a natural problem. Instance: Positive integers, $d_1,\ldots,d_n$ and $k$, all bounded from above by $n$. Question: Does there exist a $k$-colorable graph with ...
user avatar
8 votes

Natural NP-complete problems with "large" witnesses

I came along some quite natural NP-complete problems that seemingly require long witnesses. The problems, parameterized by integers $C$ and $D$ are as follows: Input: A one-tape TM $M$ Question: Is ...
user avatar
  • 532
8 votes

Natural NP-complete problems with high density?

Comment => Answer. In this paper, Posa shows that for some constant $c$, a graph chosen from the Erdos-Renyi random graph distribution $G(n, c \log n / n)$ has a Hamiltonian cycle with probability ...
user avatar
  • 1,624
8 votes

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 ...
user avatar
8 votes
Accepted

Does p-isomorphism preserve phase transition?

Yes, but I'm not sure it means much. Yes in a trivial way: suppose $\varphi$ is an isomorphism between two $\mathsf{NP}$-complete languages $L_1, L_2$, and $L_1$ exhibits a phase transition with ...
user avatar
8 votes
Accepted

Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis

First of all, Mahaney's Theorem says that merely assuming $\mathsf{P} \neq \mathsf{NP}$, there are no sparse $\mathsf{NP}$-complete sets. (Historically, Mahaney was motivated to study this precisely ...
user avatar
8 votes
Accepted

Is there any relationship of hardness between the two problems?

No, you cannot infer hardness of P1. (And your question looks suspiciously close to homework.) Consider the special case where $D$ is an undirected graph $G=(V,E)$ $x$ is a subset $E_x\subseteq E$ $...
user avatar
  • 5,712
8 votes

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 ...
user avatar
8 votes
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 ...
user avatar
  • 778
7 votes

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 ...
user avatar
  • 7,052

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