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, ...
Joshua Grochow's 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 ...
Ryan Williams's user avatar
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 ...
Neal Young's user avatar
  • 9,595
13 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 ...
David Eppstein's 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 ...
Ryan Williams's 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 ...
William Hoza's 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/...
Bartosz Bednarczyk's 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 ...
D.W.'s user avatar
  • 11.7k
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 ...
Gamow's user avatar
  • 5,772
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 ...
Klaus Draeger's user avatar
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. ...
David Eppstein's 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 ...
Joshua Grochow's user avatar
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 ...
Sahil Singla's 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 $...
daniello's user avatar
  • 3,256
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 ...
Andrej Bauer's user avatar
  • 28.3k
8 votes
Accepted

Is Circuit Minimization $P$-hard under logspace reductions?

The Circuit Minimization Problem you describe is also known as MCSP (the Minimum Circuit Size Problem), which has been the subject of quite a few papers recently. (I'm posting an answer to this ...
Eric Allender's user avatar
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,...
Joshua Grochow's user avatar
7 votes
Accepted

Is iszero of the untyped lambda calculus sound and complete?

No, iszero does not have to test whether two functions are equal. It only has to detect a difference between them, i.e., extract enough information to tell whether ...
Andrej Bauer's user avatar
  • 28.3k
7 votes

Polynomial-time reductions between undecidable languages

Gödel's incompleteness theorem can be thought of as a reduction from the Halting problem to the language $\langle \varphi \mid \varphi \text{ is a true sentence in number theory}\rangle$, and a ...
Joe Bebel's user avatar
  • 2,295
7 votes

Calculus of Constructions: compress expression to its smallest form

As Andrej has said, the problem is undecidable if you allow replacing one term by another, extensionally equal one. However, you might be interested in optimal sharing of expressions, in the following ...
cody's user avatar
  • 13.7k
7 votes
Accepted

Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (...
Sasho Nikolov's user avatar
7 votes

Reductions in Descriptive Complexity

Standard notions of reduction used in Descriptive Complexity are first-order reduction and the weaker first-order projection. Definitions of both these notions are found in Immerman's book on ...
Jan Johannsen's user avatar
7 votes
Accepted

Complexity of reachability in directed rooted forests

The problem is L-complete. It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that ...
Emil Jeřábek's user avatar
6 votes

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

(I understand this must be a late answer; i am writing for future readers) There is an evern stronger result in the literature. Cubic Planar Positive 1-in-3 Satisfiability is proved NP-complete in ...
Cyriac Antony's user avatar
6 votes
Accepted

$\mathsf{TC^0}$-completeness and reductions

For question #1: If there is a complete problem for uniform TC$^0$ under uniform AC$^0$ m-reductions, then the counting hierarchy collapses. I don't know if this qualifies as "bad". For ...
Eric Allender's user avatar
6 votes

Calculus of Constructions: compress expression to its smallest form

Let me insist on the viewpoint touched upon by cody's answer. As far a see it, the question of finding a smallest $\lambda$-term equivalent to another $\lambda$-term is not really interesting, even ...
Damiano Mazza's user avatar
6 votes
Accepted

Reducing 3-XOR-SAT to HORN-SAT

The question is not very clear, as equisatisfiability of individual clauses does not imply equisatisfiability of the whole formulas. However, if you mean a construction where each XOR clause is ...
Emil Jeřábek's user avatar
6 votes
Accepted

Proving not NP-complete by non-existence of gadget

First, I agree w/ Ludwik & other comments that I think (i) is unlikely. Polynomial-time reductions are just polynomial-time algorithms satisfying a certain (fairly flexible! compared to say p-time ...
Joshua Grochow's user avatar
5 votes
Accepted

Complexity of permanent modulo prime

First, the permanent of an $n\times n$ integer matrix with $O(n)$-bit coefficients is an integer with $O(n^2)$ bits, hence if we know it modulo an integer with $\Omega(n^2)$ bits (with the implied ...
Emil Jeřábek's user avatar

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