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, ...
user avatar
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-...
user avatar
16 votes

Should reductions make us more or less optimistic for the tractability of a problem?

What is missing from the analogy is some notion of the relative distances involved. Let's replace Alaska in our analogy with the moon: You're an explorer, searching for a bridge between the North ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,968
14 votes
Accepted

Should reductions make us more or less optimistic for the tractability of a problem?

I think this is a very good question. To answer it we need to realise that: not all reductions are alike, to feel optimistic, we need to learn something genuinely helpful. Typically, whenever we ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$...
user avatar
  • 2,267
13 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 ...
user avatar
  • 8,133
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 ...
user avatar
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 ...
user avatar
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/...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,733
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/...
user avatar
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 ...
user avatar
  • 10.3k
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^...
user avatar
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; ...
user avatar
  • 4,584
9 votes

Should reductions make us more or less optimistic for the tractability of a problem?

It is not true that we always look at reduction theorems as hardness statements. For example, in algorithms we often reduce a problem to LP and SDP to solve them. These are not interpreted as ...
user avatar
  • 21.3k
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 ...
user avatar
  • 881
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 5,712
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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 $...
user avatar
  • 3,161

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