Tag Info

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, ...
• 35.6k
Accepted

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

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 ...
• 3,211
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 ...
• 26.2k

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
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 ...
• 11.3k

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 ...
• 22.3k
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 ...
• 9,556

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,267
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 ...
• 8,133
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 ...
• 22.3k
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 ...
• 50.2k

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/...
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, ...
• 22.3k

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 ...
• 26.2k
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,733
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/...
• 1,110
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.3k