Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,594
questions
0
votes
0answers
58 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 ...
-2
votes
0answers
46 views
Which polynomial time dynamic programming problems are in $NC$?
Here ftp://html.soic.indiana.edu/pub/techreports/TR424.pdf Matrix chain multiplication which is usually solved using dynamic programming is solved in $NC$.
This brings to the problem of which classes ...
6
votes
1answer
85 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.)?
8
votes
0answers
226 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 (...
1
vote
1answer
95 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
217 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
264 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
41 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 ...
-3
votes
0answers
90 views
$SAT$ solvability via strongly polynomial time simplex algorithm?
Are there classes of $SAT$ problems cast as integer programming solvable by parametrized strongly polynomial time simplex algorithm versions such as https://www.tandfonline.com/doi/full/10.1080/...
2
votes
0answers
81 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
129 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
61 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
147 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
62 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
79 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
80 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
29 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
148 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
58 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
83 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
44 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
110 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
284 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
222 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
54 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
792 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?
1
vote
0answers
165 views
Can a hash preimage be used to amplify BPP probabilities?
Suppose we are given a (univariate) polynomial $P$ of degree $d$, and we wish to determine if $P$ is identically $0$. A standard way to do this is to use a classical PRG to randomly sample a number $...
2
votes
1answer
143 views
Is the unbounded fan-in model realistic?
Does the unbounded fan-in circuit model apply in "practical" settings? In other words, are there real-world realisable computers with unbounded fan-in gates?
As I understand, standard silicon ASICs ...
-1
votes
1answer
84 views
Comprehensive list of functions used in Big-$O$ notation
We all know that exponential functions grow faster than polynomials. Let us consider the following function: $f(n)=n^{a_1}⋅(\log n)^{a_2}⋅(\log\log n)^{a_3}⋅(\log\log\log n)^{a_4}⋯ $ where the leading ...
2
votes
2answers
195 views
Under what models do we know linear time sorting?
The best we know for general case sorting is $O(n\log n)$ (which is also $\theta(n\log n)$ is decision tree model) and the problem of $O(n)$ sorting is open for turing machine models.
Under what ...
20
votes
1answer
411 views
Is prime-counting function #P-complete?
Recall $\pi(n)$ the number of primes $\le n$ is the prime-counting function. By "PRIMES in P", computing $\pi(n)$ is in #P. Is the problem #P-complete? Or, perhaps, there is a complexity reason to ...
2
votes
0answers
56 views
$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?
Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following:
$FPT = XPuniform\implies EPTAS = PTAS$.
Fundamentals of Parametrized complexity on page $534$ has
...
2
votes
0answers
133 views
Is the following problem in $coNP$?
Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$?
At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
0
votes
0answers
44 views
What is the complexity of Parametric Mixed Integer Linear Programming?
We know
$$\forall\bf y\in\mathbb Z^n:K\bf y\leq b$$
$$\exists\bf x\in\mathbb Z^m:A\bf x + B\bf y\leq c$$
is in $\bf P$ if $n,m$ are fixed from Kannan's result (refer page $1$ in reference).
What is ...
8
votes
3answers
394 views
Why exactly are complexity theorists interested in closed timelike curves?
Context:
There are several papers that study the implications of closed timelike curves (CTCs) to quantum complexity. In 2008, Aaronson and Watrous published their famous paper on this topic which ...
2
votes
1answer
120 views
Lower bound on alternations needed in $BQP$ versus $PH$ result?
What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
4
votes
1answer
170 views
Which (almost) balanced Boolean function has smallest “total” influence
The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$
$$
\max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot ...
8
votes
1answer
255 views
Is there any quantum analog of the VP vs. VNP problem?
From Wikipedia:
$\mathsf{VP}$: The class VP is the algebraic analog of P; it is the class of polynomials $f$ of polynomial degree that have polynomial size circuits over a fixed field $K$.
$\...
-1
votes
1answer
80 views
Why is $BPP^{NP}$ in polynomial hierarchy? [closed]
Why is $BPP^{NP}$ in the polynomial hierarchy?
I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. However, how does that imply $BPP^{NP}$ is inside the polynomial hierarchy?
2
votes
1answer
66 views
Hardness of LWE on not-uniform vector samples
The "usual decisional LWE":
The challenger and the adversary get a common random matrix $A \in F_{q}^{m \times n}$. The challenger chooses a secret $s \in F_{q}^{n}$ and generates random (small) ...
2
votes
1answer
114 views
How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time? [closed]
In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm ...
10
votes
1answer
291 views
How hard is deciding the existence of Red-Blue perfect matching?
Two-colorable perfect matching problem is to decide whether a graph has coloring with two colors such that each node has exactly one neighbor the same color as itself. The problem was proven to be NP-...
10
votes
1answer
358 views
An obstruction like ETH
We know under $ETH$ we cannot solve $K$-SUM in $f(K)poly(nK)$ time under any function $f(K)$ (usually $2^{O(K)}$).
Is there any conjecture that prevents a $(\log n)^{O(K)}$ complexity (this is ...
2
votes
0answers
117 views
A complexity-class of problems that cannot be solved in finite time
Consider the following game: Alice chooses a real function number $x\in [0,1]$; Bob has to guess the number by asking Alice any number of queries of the form "is $x > a$?" [where Bob can choose ...
11
votes
1answer
599 views
Technical issue with PCP theorem proof
I am reading the proof from here and I stumbled upon a technical (yet crucial) problem. I know this is rather specific and the context is problematic, but I couldn't figure it out myself.
In pages 51 ...
11
votes
0answers
154 views
$\exists \mathbb R$ and IP
We know NP$\subseteq$ $\exists \mathbb R$$\subseteq$ PSPACE=IP, but is there some more direct proof for $\exists \mathbb R\subseteq$ IP?
What about the other direction, are there some Arthur-Merlin ...
1
vote
0answers
75 views
Minimum cut with nonlinear objective function
Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum.
Let us generalize it the following way: let $f$ be a ...
3
votes
0answers
83 views
Counting quotient graphs, but not exactly
All graphs considered will be directed graphs $G=(V,E)$, with $E \subseteq V \times V$ (so possibly with self-loops). For $k \in \mathbb{N}_{\geq 1}$, I will write $[k]$ the set $\{1,\ldots,k\}$. A $k$...
