New answers tagged cc.complexity-theory
0
Here's an answer to the two secondary questions at the end, regarding similar problems:
Problem 1. In an edge-weighted graph, is there a Hamiltonian-cycle with a unique weight?
Problem 2. If we have a CNF-SAT formula with weights assigned to every variable assignment, is there a unique weight satisfying assignment?
These are of course at least ...
1
A (counter)example from the recent research literature: almost every simply typed $\lambda$-calculus term has a long $\beta$-reduction sequence (Asada et al., 2019), but this property is very hard to test, even if P = NP!
Asymptotically, almost every STLC term of order $k$ and length $n$ has reduction sequence length $(2\uparrow \uparrow (k - 1))^{\Theta(n)}...
1
Constructing unsatisfiable 3SAT problems isn't that hard if you just build up to whatever you're looking for. For example let's start with a base requirement.
An equation equal to A & !A is unsatisfiable. It's actually the only thing that's unsatisfiable. So we're trying to write a system of equations that forces this relationship.
Next we'll examine ...
3
The problem of finding the shortest simple cycle through two vertices in a weighted undirected graph can be solved in the same time as Dijkstra's algorithm for a single shortest path, by applying Suurballe's algorithm for finding disjoint $s$–$t$ shortest paths in a directed graph.
It doesn't quite work to turn your given undirected graph directed by ...
5
Yes, this problem is FPT. We showed this in the paper "Parameterized Edge Hamiltonicity" (Lampis, Makino, Mitsou, and Uno, DAM 2018).
In particular, in this paper we state the result for Hamiltonian Path, but things doesn't change much if you want to consider Hamiltonian Cycle. In the conference version (and the slightly outdated version on the arxiv) we ...
5
I think the scaling $2^{n/q^c}$ is too much to ask for. Even $poly(q) 2^{O(n-q)}$ would represent an exponential speedup for each additional qubit.
And indeed, such a problem is known: simulating a quantum circuit of $n$ logical qubits on a small hybrid quantum-classical computer with only few (perfect) physical qubits $q\leq n$ has this scaling. See: ...
0
It's quite common for properties split numbers into "almost all" and "almost none" sets. For instance, almost none of Turing machines halt. Almost all real numbers are normal. Almost none of real number are algebraic.
1
Yes, the counting version of 1-in-3 Sat is $\#P$-complete. This is stated in "Complexity of Generalized Satisfiability Counting Problems" (Example 3.1), the reference pointed out by Emil in the comment.
Note:
This leads us to the curious question: is the counting version of every NP-complete problem $\#P$-complete? The answers to this question (When does &...
19
They are separate (assuming $P \ne NP$). Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance of 3SAT. It's clear that testing whether $x$ satisfies $P$ is NP-hard, yet almost all strings satisfy it: the density $\to 1$ as $n \to \infty$.
9
This isn't my area, so many apologies if I say something incorrect:
1) "What evidence do we have that $\mathsf{BPP}\subseteq \mathsf{REXP}$?"
Isn't this unconditionally true? It should follow from $\mathsf{BPP}\subseteq \mathsf{EXP}$, and in fact by Sipser-Gács-Lautemann $\mathsf{BPP}\subseteq \Sigma^p_2\cap \Pi_2^p$.
2) "What consequences does $\mathsf{...
Top 50 recent answers are included
