Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
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$...