27 votes
Accepted

Does Karp reducibility yield a total order?

Far from it. Indeed, any countable distributive lattice embeds as a sub-partial-order of $\leq_p$, even if we only consider those degrees in between two given fixed languages (K. Ambos-Spies, ...
22 votes
Accepted

Curious about computer-assisted NP-completeness proofs

As for question 2, there are at least two examples of $NP$-completeness proofs that involve computer-assistant. Erickson and Ruskey provided a computer-aided proof that Domino Tatami Covering is NP-...
16 votes
Accepted

Is ALogTime != PH hard to prove (and unknown)?

Not sure why Fortnow says there's "no meaningful model where $L$ and $NP$ collapse"... it seems to me that QBF should make them collapse, under the usual Ruzzo-Simon-Tompa oracle model (and the link ...
15 votes

Curious about computer-assisted NP-completeness proofs

In this paper, I showed that if for some $k\geq 3$ there is a graph with maximum degree $k$ and chromatic edge strength strictly greater than $k$, then it is $\Theta_2^p$-complete to decide if ...
  • 1,968
14 votes
Accepted

Are there subexponential algorithms for PLANAR SAT known?

Well, you can apply the planar separator theorem together with dynamic programming and get running time $2^{O(\sqrt{n})}$, where $n$ is the number of vertices in the graph. The idea being that you try ...
14 votes

Curious about computer-assisted NP-completeness proofs

From the comment above: I used the Choco Java library for Constraint programming to check the correct behaviour of the gadgets used to prove the NP-completeness of the following puzzles: Binary ...
14 votes
Accepted

Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?

You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious. For the record, here's a sketch of a reduction that is parsimonious. It is obtained by composing ...
  • 9,024
13 votes

How to prove that USTCONN requires logarithmic space?

The paper Counting Quantifiers, Successor Relations and Logarithmic Space, by Kousha Etessami proves that the problem $\mathbf{ORD}$ (which is essentially checking if a vertex $s$ precedes a vertex $t$...
  • 2,289
12 votes
Accepted

Limited number of variable occurrences in 1-in-3 SAT

Up to my knowledge the current "limits" have been settled in: Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer, Andreas Wotzlaw: XSAT and NAE-SAT of linear CNF classes. Discrete Applied ...
12 votes
Accepted

Is intersection of $k \ge 3$ graphic matroids in P?

I think it is still NP-complete, by a reduction from Hamiltonian paths in bipartite graphs with two degree-one vertices and all other vertices having degree three. (This is just the same as finding ...
11 votes

Curious about computer-assisted NP-completeness proofs

I did this very thing — computer-assisted NP-completeness proof — in my bachelor thesis! The bad part - it's in Russian and wasn't translated to English. http://is.ifmo.ru/diploma-theses/...
11 votes
Accepted

Proof for Kolmogorov complexity is uncomputable using reductions

You can find two different proofs in: Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995) In Li, Ming, Vitányi, ...
11 votes

On reducing the hardness of CNF-SAT to k-Clique

I don't know the answer to your specific question (it seems related to the question of whether W1=W[2]). But the algorithm you give in your question is subsumed by several other results. Using your ...
11 votes
Accepted

On sparse complete sets and P vs L

Yes, exactly what you suggested is true: if there is a sparse $\mathbf{P}$-complete set under log-space many-one reductions, then $\mathbf{P} = \mathbf{L}$. This was conjectured by Hartmanis in 1978 ...
  • 1,743
11 votes
Accepted

Existing implementation of Scott's reduction?

You might check the FO2 solver by Tomer Kotek et. al (ICDT 2017): https://forsyte.at/alumni/kotek/fo2-solver/ as well as an FO2 solver by Tony Tan and his students (LICS 2021): https://arxiv.org/abs/...
10 votes
Accepted

Improving Cook's generic reduction for Clique to SAT?

You can express $k$-clique as a SAT instance with $O(nk)$ variables and $O(nk^2)$ clauses. For fixed $k$, this is linear in $n$. Let $x_{iv}=1$ if $v$ is the $i$th vertex in the clique (by ...
  • 10.8k
9 votes
Accepted

Reducing sorting to max-flow

It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow ...
9 votes
Accepted

The relationship between completeness and strength of reductions

If I understand correctly your questions are answered in Agrawal-Allender-Impagliazzo-Pitassi-Rudich-2001: Reducing the Complexity of Reductions Gap Theorem - Any set that is NP-complete under $AC^...
9 votes

Reduction SAT to a problem on a planar graph with as few vertices as possible

You are right that improved reductions from CNF-SAT to any one of various planar graph problems would give improved algorithms for CNF-SAT (via graph algorithms with runtimes exponential in treewidth; ...
  • 4,604
9 votes
Accepted

Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?

Let me clarify the question a bit first: Agnostic learning conjunctions is known to be NP-hard only if the learner needs to be proper (output a conjunctions as a hypothesis) and work for any input ...
  • 881
9 votes

Verifying a subtlety of Karp's original proof that SAT has a polynomial time reduction to 3SAT

The conjunction of the first two clauses, $(\sigma_1\cup\sigma_2\cup u_1)(\sigma_3\cup\ldots\cup\sigma_m\cup\bar{u}_1)$ is equisatisfiable to the original clause, as can be easily checked (any ...
9 votes
Accepted

Validity of exponentiation in a polynomial time reduction

The proof as presented in the paper is not conclusive. However, the stated result itself is correct. It can easily be derived by slightly changing the reduction and by using SUBSET PRODUCT instead of ...
  • 5,742
9 votes

Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. ...
8 votes
Accepted

#P- vs PP-Completeness

Not necessary. Imagine the following Fake-#SAT problem: possible solutions are extended by one bit, and all vectors with this bit set are solutions. That is, the number of satisfying assignments for ...
  • 250
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

Reductions between languages of different densities?

Let $A$ be any language not in $L$, such that $A$ has density $2^{o(n)}$, and define $$B = \{s \circ 1 | s \in \{0,1\}^*\} \cup \{s \circ 0 | s \in A\}.$$ Here $\circ$ is concatenation. The language $...
  • 3,236
8 votes

Is intersection of $k \ge 3$ graphic matroids in P?

How about using the fact that 3-d matching is NP complete to show NP Completeness of this problem. We can easily write 3-d matching as intersection of 3 partition matroids, and a partition matroid is ...
8 votes
Accepted

Calculus of Constructions: compress expression to its smallest form

There's a bit of freedom in what we considre "the same value". Let me show that there is no such algorithm if "the same value" means "observationally equivalent". I will use a fragment of the Calculus ...
  • 26.9k
8 votes
Accepted

Is solving the following system of boolean equations NP-hard?

[Now that the question's been clarified I'll post my previous comment as an answer.] It's in $\mathsf{P}$. Start with unit propagation. Afterwards, what's left on the right-hand sides will be monotone,...

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