Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
824 questions with no upvoted or accepted answers
50
votes
0
answers
2k
views
Monotone complexity of s-t connectivity
In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between all $n^2$ pairs $...
- 6,815
48
votes
0
answers
1k
views
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice ...
- 3,732
34
votes
0
answers
1k
views
Is BPP= P known for ANY uniform model of computation?
Many believe that BPP $=$ P "should" hold for Turing machines. We even have some "witnesses" for this: otherwise some "strange" things would happen; see e.g. this paper by Implagliazzo and Wigderson.
...
- 6,815
31
votes
0
answers
808
views
The complexity of checking whether two DAG have the same number of topological sorts
This problem is highly related to the CNF one.
Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".
...
- 719
29
votes
0
answers
1k
views
Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?
By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.
I think this is a proof: if $EXP\...
28
votes
0
answers
745
views
Is Hankelability NP-hard?
I asked this question on SO on April 7 and added a bounty which has now expired but no poly time solution has been found yet.
I am trying to write code to detect if a matrix is a permutation of a ...
- 3,932
27
votes
0
answers
1k
views
Counting Isomorphism Types of Graphs
Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
- 5,823
23
votes
0
answers
520
views
Fine-grained complexity of BPP
If E does not have i.o.-$2^{o(n)}$ circuits, then P=BPP, but this does not tell us about the fine-grained containments between $\mathrm{Time}(n^a)$ and $\mathrm{BPTime}(n^b)$.
Are there reasonable ...
- 2,742
22
votes
0
answers
801
views
What is the power of general poly-size permutation branching programs?
Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
- 5,638
21
votes
0
answers
283
views
Descriptive complexity characterization of TimeSpace classes
Are there descriptive complexity characterizations for TimeSpace complexity classes like $\mathsf{SC^i}= \mathsf{DTimeSpace}(n^{O(1)},O(\lg^i n))$?
- 21.9k
20
votes
0
answers
709
views
Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?
The following question arose as a side product of some work I have been part of recently.
An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a ...
- 3,932
20
votes
0
answers
490
views
Interesting PCP characterization of classes smaller than P?
The PCP theorem, $\mathsf{NP} = \mathsf{PCP}(\mathsf{log}\, n, 1)$, involves probabilistically checkable proofs with polynomial time verifiers, so the smallest class that can be characterized in this ...
- 2,291
20
votes
0
answers
591
views
Complexity of finding the smallest well-covered completion
This is related to an earlier question on which graphs have the property that all maximal independent sets are maximum — such graphs turn out to be known as the well-covered graphs. Any graph $G$ is ...
- 51.2k
20
votes
0
answers
505
views
Model-checking for three-variable logics and restricted structures
Denote the $k$-variable fragment of logic $L$ by $L^{(k)}$. The model-checking problem for a logic $L$ with respect to a class of structures $C$, denoted $MC(L,C)$, is the decision problem
$MC(L,C)...
- 19.2k
19
votes
0
answers
574
views
Courcelle's theorem for bounded clique-width graphs
Courcelle's theorem states that "Every graph property which is expressible in monadic second order logic is decidable in linear time for bounded tree-width graphs". Later it was extended to bounded ...
- 2,044
19
votes
1
answer
2k
views
Complexity of interval cover problem
Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to ...
- 191
18
votes
0
answers
525
views
Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?
Question 1: Is it true that for every polynomial $p(n)$ and $\epsilon >0$ there is a polynomial $q(n)$ such that every monotone Boolean function on $n$ variables that can be expressed by a Boolean ...
- 5,823
18
votes
0
answers
380
views
Descriptive complexity of communication complexity classes
It is well known that some major complexity classes, like P or NP, admit a full logical characterization (e.g NP = existential 2nd order logic by Fagin's theorem). On the other hand, one can also ...
- 2,806
17
votes
0
answers
398
views
Intermediate problems between PSPACE and EXPTIME
Intermediate problems between P and NP are quite famous, and are sometimes considered as complexity classes by themselves.
Do you know of any problem that is known to be PSPACE-hard and in EXPTIME, ...
- 9,028
17
votes
0
answers
990
views
Deeper look at Algorithmica?
Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995.
He presented five possible worlds we could be living in, depending on how P and NP were related.
The ...
- 19.2k
17
votes
0
answers
494
views
Can short-distance connectivity be harder than connectivity?
Has anybody seen the following (or similar) question being considered:
Can it be easier to determine the presence/absence of $s$-$t$ paths than to determine the
presence/absence of short $s$-$t$ ...
- 6,815
17
votes
0
answers
790
views
Practically Good Algorithms of a Very Low Computational Complexity Class
I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties:
1) Solving the ...
- 5,823
17
votes
0
answers
518
views
What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?
Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows.
Is there a result comparable to the Karp-...
- 5,638
17
votes
0
answers
438
views
Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?
I am interested in the following problem.
Node Multiway Cut on Planar Graphs with terminals on the outer face
Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals which ...
- 5,285
17
votes
0
answers
325
views
Problem-Dependent Derandomization
The famous result of Impagliazzo and Wigderson in '97 cemented our belief that BPP is most likely the same as P; that is, problems that can be efficiently solved with randomness can also be ...
- 3,888
17
votes
0
answers
368
views
complexity of checking if a subspace is a Euclidean section of L1
If $X$ is a linear subspace of ${\mathbb R}^n$, $X$ is high-dimensional, and for every $x\in X$ we have
$(1-\epsilon) \sqrt n ||x||_2 \leq ||x||_1 \leq \sqrt n ||x||_2$
for some small $\epsilon >...
- 4,952
16
votes
0
answers
546
views
Quantum Hardness of Finding Nash Equilibria
This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen.
Their main result is that the existence of ...
- 6,081
16
votes
0
answers
495
views
Is graph coloring complete for poly-APX?
Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
- 6,795
16
votes
0
answers
1k
views
Phase Transitions in NP Hard Problems
SAT Problems have a phase transition that depends on the ratio $r$ of variables to clauses. Below $r$, SAT problems are solvable quickly; above, they become difficult. The same is true of NP ...
- 521
15
votes
0
answers
517
views
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For ...
- 2,742
15
votes
0
answers
392
views
Complexity of approximating the range of a matrix
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$
I believe that it is NP-hard to compute $S_M$ exactly, by applying ...
- 3,932
15
votes
0
answers
464
views
What is the evidence for average case separation between EXP and NEXP?
There is significant evidence from cryptography that there exist NP-complete problems that are hard in the average case (meaning that e.g. $AvgP \nsupseteq DistNP$). Namely, we have candidate one-way ...
- 2,181
15
votes
0
answers
522
views
Williams' Method, Natural Proofs and Constructivity
I have some questions on the previous question which is written bellow.
Natural Proof and Constructivity : The topic of the previous question
Recently, Ryan Williams proved that Constructivity in ...
- 171
15
votes
0
answers
346
views
Intersecting Complexity Classes with Advice
In on hiding information from an oracle, the authors (Abadi, Feigenbaum, and Kilian) wrote:
$(\mathsf{NP/poly} \cap \mathsf{co\text-NP}{/poly})$ ... is not known to be equal to $(\mathsf{NP}...
- 16.6k
15
votes
1
answer
2k
views
Is CFL strictly contained in NL?
We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$.
What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$?
Is $\mathsf{CFL}$ a ...
- 251
15
votes
1
answer
457
views
Characterization of read-once formulae over the full binary basis
Background
A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (...
- 13.8k
14
votes
0
answers
240
views
Counting solutions to extended MSO formulas, and sampling -- do these appear in the literature?
I am trying to determine if the literature contains various extensions of Courcelle's theorem. Since I haven't been able to find these in the literature, I guess that these are folklore results, or ...
- 1,479
14
votes
0
answers
476
views
Is there a P-complete language X such that succinct-X is in P?
I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
- 5,177
14
votes
0
answers
313
views
First use of sans serif for complexity classes
(Apologies for the triviality of this question; nevertheless, it's been bugging me and presumably people here will be able to answer it...)
It seems that it has become popular in recent years to ...
- 2,013
14
votes
0
answers
210
views
The best known upper bound for two-way probabilistic finite automata with one-counter
It is known that the class of languages recognized by two-way deterministic finite automata with one-counter (2D1CAs) is a proper subset of $ \mathsf{L} $ (deterministic log-space):
A 2D1CA can run at ...
- 3,717
14
votes
0
answers
307
views
Pseudorandom functions in ACC^0?
In the lower bound result by Ryan Williams (Non-uniform $\mathsf{ACC}$ circuit lower bounds), there is a mention of "little evidence that Pseudorandom function generators exist in $\mathsf{ACC}^0$. Is ...
- 1,364
14
votes
0
answers
284
views
AC0 many-one reduction of Mod_3 to PRIMES?
Let Mod$_3$ be the language of binary strings with the sum of the bits divisible by 3, and PRIMES be the set of prime integers.
In a 2001 paper A Lower Bound for Primality, Allender, Saks, and ...
- 19.2k
14
votes
0
answers
494
views
DPLL and Lovász Local Lemma
Let $\varphi$ be a CNF formula. Suppose that each of $\varphi$'s clauses consist of exactly $t$ literals (and, moreover, all literals within one particular clause correspond to different variables). ...
- 1,569
14
votes
0
answers
415
views
Question on Products of Graphs
Let $S_{n}(G)$, $C_{n}(G)$, $T_{n}(G)$ be the $n$-fold Strong Product, Cartesian Product and Tensor Product of a graph $G$ on $|V|$ vertices.
Let the chromatic number ($\chi(G)$) and the independence ...
- 2,228
14
votes
0
answers
327
views
Linear PRAM vs Arithmetic Linear PRAM
A linear PRAM model is a PRAM model without bit operations and at least one operand of the $\times$ instruction is a constant. If in addition we require that the running time does not depend on the ...
- 10.6k
14
votes
0
answers
276
views
Any example of an unsatisfiable integer program with non constant Rank Lower bounds for LS+ cuts but with short LS+ refutations?
Assume we want to refute an unsatisfiable CNF. We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS_{+}$ cuts) to its linear ...
- 1,851
13
votes
0
answers
424
views
Consequences of bipartite perfect matching not in NL?
Are any significant consequences known of $\text{BPM} \not\in \textsf{NL}$?
I'm interested in the status of the following well-studied decision problem, in particular whether it is known to be in $\...
- 19.2k
13
votes
0
answers
450
views
How can one find the "hard" probability distribution on the input for recursive boolean functions?
Update:
Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main ...
- 405
13
votes
0
answers
548
views
Are there any implementations of Cook-Levin?
Does anyone know if there is an implementation of Cook-Levin?
A program that gets an input like the following:
$M$: the code of a machine model/simple program in a programming language like C,
$\vec{...
- 21.9k
13
votes
0
answers
524
views
Non-deterministic logspace with two-sided error
The class BPL is the set of all problems solvable by a Turing machine running in logarithmic space and polynomial time with two-sided error; that is, if $x\in L$ then the machine accepts with ...
- 1,224