# 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. ...
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 ...
Accepted

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"...
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-...
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 ...

### "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 = ...
Accepted

### Enumerating finite set of words with Hamming distance $1$

This problem is NP-complete. The class of graphs in the question is equivalent to the cubical graphs *1, but this class contains grid graphs. Because the Hamiltonian path problem in grid graphs is NP-...

### 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 ...
Accepted

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$ $... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 7 votes ### Problems in NP with non-trivial certificate I feel like problems$P\in\mathsf{NP}\cap\mathsf{coNP}$are good examples for your question. Typically, for$P\not\in\mathsf{P}$, at least one of the witnesses is non-trivial. For example, the closest ... 6 votes ### Questions regarding SETH Cygan, Kratsch and Nederlof give a$(2+\sqrt{2})^{\texttt{pw}} n^{O(1)}$algorithm for hamiltonicity on graphs with$n$vertices and pathwidth$\texttt{pw}$(assuming you are given the pathwidth ... 6 votes ### Graph theoretic restriction to Proofs in Proof Complexity Theory For strong enough proof systems the graph representation of a proof in the system seems less consequential, since (as Joshua Grochow already commented), DAG-like and tree-like Frege proofs are ... 6 votes Accepted ### Reduction of graph chromatic number to hypergraph 2-colorability As the other answer points out, the reduction in the original paper seems to have a bug:$H$will not be two-colorable unless$G$is bipartite. I couldn't quite see how to prove the reduction in the ... 6 votes ### Implications of proving NP=RP on complexity theory A simple answer is that we're "pretty sure" that$\mathsf{P} \neq \mathsf{NP}$, and we're "pretty sure" that$\mathsf{P} = \mathsf{RP}$, so we're "pretty sure" that$\...
For general $L\in\mathrm{NP}$, this is equivalent to $\mathrm{FP=TFNP}$, hence likely false: On the one hand, if $V$ and $V'$ are verifiers of $L$, then “given $x$ and $u$ such that $V(x,u)$, find $u'$...