Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,617
questions
0
votes
0answers
21 views
How to deal with witness size when collapsing PH with $\Sigma_k \neq \Pi_k$
I'm reading Goldreich's note on PH and it notes that if $\Sigma_k \neq \Pi_k$ for some $k$, then PH collapses to the corresponding level (so $\mathcal{PH} = \Sigma_k$). At least one formulation of the ...
1
vote
0answers
72 views
An idea for finding simple cases for $\mathsf{SAT}$ problem
As I know there are relatively small number of cases when we know a
polynomial-time for $\mathsf{SAT}$. One such example is $2$-$\mathsf{SAT}$. (Is there a reference for a good survey of such ...
-2
votes
0answers
14 views
On definition and study of software delivery algorithms and related computational complexity
Recent developments around software delivery automation (often related to as continuous integration/devops) have emphasized on standardization of phases required to deliver software, differing though ...
9
votes
0answers
112 views
Is unary $\Pi_2$-SUBSETSUM coNP-complete?
Consider the following problem:
for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation
define is it true that
for every $S \subseteq \{1, ..., 2n \}$ such that $|...
8
votes
0answers
185 views
Conditional separations of $\exists\mathbb{R}$ from $\mathbf{PSPACE}$
As pointed out explicitly by Emil Jeřábek here:
Even with Turing reductions, $\mathbf{PSPACE}=\mathbf{P}^{\exists\mathbb{R}}$ would still be a breakthrough (and completely unexpected) result.
So ...
-1
votes
1answer
113 views
Evidence integer multiplication is in linear time?
After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...
0
votes
0answers
39 views
Volume computation of special polytopes
I'm interested in computing the volume of a special class of $\mathcal{H}$-polytopes and the complexity of doing so.
I know that in general it is #P-hard to compute the volume of $\mathcal{H}$
-...
4
votes
1answer
96 views
Satisfiability problems with restricted (not bounded) number of occurrences per variable
Intro
It is known that SAT is hard even when restricted to, e.g., formulas with exactly 3 literals per clause and at most 4 occurrences per variable. On the other hand it is easy if there are exactly ...
33
votes
3answers
5k views
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.
I have asked some people who are ...
7
votes
0answers
196 views
Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?
We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$.
Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$.
$\mathsf{...
8
votes
2answers
409 views
PPAD and Quantum
Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
-1
votes
0answers
66 views
Is $\Sigma_2^{NP}=NP^{\Sigma_2}$? [migrated]
Disclaimer: If not interested in my background, skip directly to the question below!
I am a complete newbie when it comes to complexity theory. I come from a physics background and I am currently ...
-3
votes
0answers
19 views
Is the variant of Exact-Cover By 3 Sets (X3C) with |C| <=2q, NP-complete? [duplicate]
In general case |X|=3q, C={C_1,C_2,...,C_m},|C|=m. Question: Is there exists an exact cover C* of X with |C*|=q?
And this problem is known to be NP-complete.
But, the restricted version of X3C ...
6
votes
2answers
178 views
Lower bound on pebbling numbers
Out of curiosity, I tried finding the original paper showing that there are graphs that require $n/\log n$ pebbles in the sense of Hopcroft, Paul, and Valiant’s seminal paper “On Time Versus Space”. (...
-1
votes
0answers
48 views
Sparsity related to linear programming in $NC$?
Linear Programming is $P$-complete. Results like here and here implies certain non-trivial cases have been parallelized.
How does complexity theory characterize $NC$ cases of linear programming?
In ...
1
vote
0answers
95 views
How to prove a general convex set is nonempty or empty in polynomial time?
The general convex set should be represented by a set of (generalized) inequalities $f_{i}(x)\leq 0 $ with $ f_{i}(x) $ being convex in $ x $.
I know ellipsoid method and interior method, but I do ...
8
votes
1answer
219 views
3-coloring planar graphs in $O\left(3^{n^.5}\right)$?
I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
6
votes
0answers
178 views
Nondeterminstic Linear Time vs Other Complexity Classes
Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?
10
votes
1answer
521 views
A game on several graphs
Consider the following game on a directed weighted graph $G$ with a chip at some node.
All nodes of $G$ are marked by A or B.
There are two players Alice and Bob. The goal of Alice (Bob) is to ...
3
votes
1answer
82 views
Complexity of existence of simple polygonalization with prescribed area?
This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
8
votes
1answer
1k views
On the sensitivity conjecture?
The recent establishment of the relation $bs(f)=O(s(f)^4)$ goes through Gotsman,Linial .
Can the same approach get to $O(s(f)^2)$ or is there an essential limitation to the approach?
14
votes
0answers
154 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 ...
2
votes
0answers
108 views
Sensitivity and Low-Degree Approximation under Non-Uniform Distribution
I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
4
votes
2answers
143 views
reference request for construction of expanders
I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson. Arora/Barak has a chapter on it, but i find it ...
2
votes
0answers
79 views
Is there any research on the complexity of producing given a problem description?
It is straightforward enough to analyze the complexity of a particular algorithm as a function of input size or other variables in terms of runtime or space used or whatever else. I am wondering if ...
6
votes
1answer
95 views
Separation of AM and SZK
Are any results on the separation of AM from SZK known (e.g. relativized separation, or a separation assuming one-way functions exist, etc.)?
9
votes
1answer
311 views
Hidden Constants in Complexity of Algorithms
For many problems, the algorithm with the best asymptotic complexity has a very large constant factor that is hidden by big O notation. This occurs in matrix multiplication, integer multiplication (...
2
votes
1answer
147 views
Possibility of hierarchy with $UP$ class?
I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The ...
-1
votes
1answer
254 views
What is the reason to use NP instead of EXP as 'the' class of intractable problems?
What is the rationale for not using EXP has the main class for intractable problems but NP? Why is it important that solutions are verifiable in polynomial time?
9
votes
4answers
322 views
Bootstrapping results that really bootstrap
There is a type of results in TCS usually called bootstrapping results. In general, it is of the form
If proposition $A$ holds, then proposition $A'$ holds.
where $A$ and $A'$ are propositions ...
1
vote
0answers
45 views
Bipartite formula complexity lower bound
I'm trying to understand the paper The Bipartite Formula Complexity of Inner Product is Quadratic, by Avishay Tal. The argument is recapped here. I am having trouble understanding the proof Theorem 3 ...
2
votes
0answers
82 views
Is equivalence of uniform AC0 decidable?
Is there a representation of the functions from $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ for which equivalence is decidable?
Since the languages defined by nondeterministic pushdown automata ...
5
votes
1answer
137 views
Is sorting pairwise distances as hard as sorting arbitrary points?
If we have $n$ points in $\mathbb{R^d}$, what is the complexity of sorting the $O(n^2)$ pairwise distances?
Clearly the complexity is $\Omega(n^2)$ but is there a reduction to show it is as hard as ...
2
votes
0answers
67 views
reduction from SAT to approximate set cover
I read this neat result proved in the early 90s:
For any $c>1$, There's a poly time map from boolean formulas $\varphi$ to
pairs $K, \mathcal S$ where $K$ is a positive integer and $\mathcal S$ ...
6
votes
1answer
153 views
complexity of deciding whether there's a small polynomial with a given root
Let $f\in (\mathbb{Z}/p\mathbb{Z})^\ast$ be a nonzero element of a prime finite field. For $d, r\in \mathbb{N}$ consider the problem of deciding whether there is a nonzero polynomial $$P(x) = a_0 +...
0
votes
0answers
65 views
Unknown gaps in computation models
I'm looking for computatuon models where it is known that there are problems that we can solve in time T1 and T2.
where T1 is smaller then T2 and it is unknown if there are problems where their ...
0
votes
1answer
89 views
How to build comparison operator (comparator) in an arithmetic circuit
I am trying to convert a basic program into an arithmetic circuit. I am stuck on the step of converting the greater than operator into an arithmetic circuit. To be specific, I do not know how to ...
2
votes
1answer
86 views
Upper bounds on the circut depth
Suppose $f:\{0,1\}^n \to \{0,1\}$ is a function such that it can be computed by a circuit of size $n^c$ for some constant $c>0$.
Q. Is there any nontrivial upper bound on the depth of a circuit ...
33
votes
10answers
5k views
Most important new papers in computational complexity
We often hear about classic research and publications in the field of computational complexity (Turing, Cook, Karp, Hartmanis, Razborov etc). I was wondering if there are recently published papers ...
2
votes
0answers
31 views
“Planar graph coloring is not self-reducible” is this about all $p$-relations encoding that problem?
I have a question about the paper "Planar graph coloring is not self-reducible" by Samir Khuller and Vijay Vazirani.
The final theorem in that paper states that "Planar Graph k-coloring is not self ...
0
votes
1answer
159 views
Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?
If $P=PP$ then the counting hierarchy collapses to $CH=P$. Because so many complexity classes are contained in $CH$, this causes most classes to now be contained in $P$. My question is whether this is ...
3
votes
0answers
64 views
Example of a hardness-of-approximation proof which improves the approximation factor?
Are there any examples of hardness-of-approximation reductions where we get a better hardness bound for the problem we've reduced to than the problem we've reduced from? In the examples I've seen so ...
0
votes
0answers
84 views
Is it possible to sort by only knowing the sign of pairwise sums?
I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
2
votes
0answers
81 views
Is $MSB$ of permanent and certifying half number of witnesses easy?
Can there be a $P$ algorithm to decide if number of perfect matchings is at least $(n!/2)+1$ for a bipartite graph on $n+n$ vertices?
Can there be a $P$ algorithm to decide if number of witnesses ...
3
votes
0answers
46 views
Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles
Definition: Define the $k$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $k$ distinct Hamiltonian cycles.
Question: Is there some constant $k$ so that the $...
1
vote
1answer
118 views
Count satisfying assignments of CNF formulas over all possible negation assignments
Consider the set of all CNF instances that can be generated by adding negations to a single monotone CNF instance. How hard is it to compute the sum of the counts of satisfying assignments for the set?...
7
votes
1answer
301 views
Planar Exact Cover by even-size sets
Major edit on June 6, 2019: Replaced the target problem with a simpler (but equivalent) one.
Is the following problem NP-complete?
Planar Exact Cover by even-size sets
Input: A set $U$, a ...
6
votes
2answers
228 views
Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power
It seems to be a folklore that we can "handle" $\textrm{ACC}[q]$ circuits not only for prime $q$ but prime power $q$.
For example, authors of this paper say that
... any constant
depth circuit ...
1
vote
0answers
56 views
Graph automorphism with prescribed values
Consider a graph $G$ with vertices labeled $1,...,n$ and edge weights $w_{ij}$. Recall an automorphism of G is a permutation $\sigma$ of the vertex labels such that $w_{\sigma(i),\sigma(j)}=w_{ij}$ ...
4
votes
2answers
807 views
Attempted proofs of P vs NP
What are the most recent (say in the last 3 years) attempts at disproving $P = NP$, and where can I find the papers?
