# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

3,066 questions
Filter by
Sorted by
Tagged with
70 views

### Proof of coNE ⊆ NE/poly

I'm finding it hard proving that NE/poly contains coNE which is backed by Complexity Zoo. It states that we can use the proof for NEXP/poly containing coNEXP but the link to the reference paper ...
69 views

### Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

We know that $\mathsf{BPP}$ is in $\mathsf{\Sigma^P_2\cap \Pi^P_2}$ by Sipser-Lautemann, as this proof relativizes we can get $\mathsf{BPP^{NP} \subseteq \Sigma^P_3\cap \Pi^P_3}$, but are there any ...
462 views

### Bijection between NP-complete problems

If $A$ and $B$ are NP-complete problems, is there a bijective function $f$ (computable in polynomial time) such that $w\in A$ iff $f(w)\in B$?
1 vote
173 views

47 views

### Hardness of deciding fractional chromatic number at most $k$

I want to find a reference for the following statement. Here, $\chi_f(G)$ denotes the fractional chromatic number of a graph $G$. For every fixed $r>2$, deciding $\chi_f(G) \leq r$ for a given ...
88 views

### On mod $2^i$ $+$-reducibility of permanent

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
59 views

### Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and ...
53 views

### Why can't we just reduce from Bounded HALT to Bounded PCP?

We know that: PCP is famously undecidable (as it can encode any DTM), but Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and Bounded-PCP (there is a matching ...
54 views

### NTM preserving modular number of accepting paths

Given a prime $p$ and an NTM with number of accepting paths $g$, is it possible to construct an NTM with number of accepting paths $g\bmod p$ in polynomial time where by $g\bmod p$ I mean the ...
52 views

### Graph theoretic problems complete for certain counting classes

What are some graph theoretic problems complete for SpanL, TotL, OptL classes? SpanP, TotP, OptP classes?
1 vote
152 views

### Relation between $k$-sum failure and $P=NP$

If $P=NP$ then $W[1]=FPT$ holds. Hence $k$-sum conjecture fails at a finite $k$. What can we say about the time complexity of $SAT$ and the lowest $k$ at which $k$-sum conjecture fails? In particular, ...
35 views

### NP vs QuasiP and W[1] vs FPT

If $F[1]=WPT$ then ETH is false. The converse is unknown (https://en.wikipedia.org/wiki/Exponential_time_hypothesis#Structural_complexity). How about the strong assumption of $NP\subseteq QuasiP$? ...
56 views

47 views

523 views

### Connection between PCP and L=SL

The book by Arora and Barak contains in chapter notes on PCP We note that Dinur's general strategy is somewhat reminiscent of the zig-zag construction of expander graphs and Reingold's ...
409 views

### Resource-bounded variant of Kolmogorov complexity

Consider the variant of Kolmogorov complexity, where the program is only allowed to use a bounded amount of resources. This more closely resembles the practical situation, where decompression needs ...
94 views

### Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
113 views

### How to intuitively express the hardness of Minicrypt and Cryptomania?

My question is as stated in the title. To give an example of “intuitively express”, it’s like: we often say Algorithmica means “NP is easy”, Heuristica means “NP is hard on worst-case but easy on ...
306 views

### Cheap online selection with weighted comparisons

Suppose we want to find the smallest element of a set $S$, whose elements are indexed from $1$ to $n$. We do not have access to the values of these elements, but we can compare any two elements of $S$...
1 vote
99 views

### Why does the Time Hierarchy Theorem fail relative to promise problems?

Define Program Evaluation (PE) to be the promise problem of determining whether a program (written in a Turing-complete language) returns True or False. The promise is that the program will return ...
252 views

### Is GCT still active?

Is Mulmuley's geometric complexity theory program still active? I tried to look it up online, and I haven't seen anything from the last couple of years.
1k views

### Law of the Excluded Middle in complexity theory

A recent blog post by Lance Fortnow discusses non-constructive proofs, where "non-constructive" here means that the law of the excluded middle is used in a substantive way. That is, one ...
188 views

### Research masters programs in theoretical computer science (with a focus on complexity theory)

I am in my 2nd year of my Computer Science degree. I am deeply interested in Complexity Theory, and I plan to pursue a career in this field I am from South Asia, and research here is not up to par, ...
689 views

### Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Do we know any problem that satisfies the following criteria? It is polynomial-time solvable on trees. It is NP-complete when restricted to graphs of treewidth 2. The problem can be encoded only ...
36 views

### converting K-SAT clause to a p-in-L-SAT equation

Given a generic K-SAT instance $S$ with $n$ boolean variables. Is it possible to convert a clause of this instance into an equivalent p-in-L SAT system of equations such that the number of new clauses ...
74 views

### Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?

Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
83 views

### Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

Wikipedia lists HSP problems in abelian and non-abelian groups. So does the following (extensive) compedium. I searched and found none is a BQP-complete (or even BQP-hard) problem. There has been a ...
1 vote
472 views

### Is it known that P $\neq$ NP implies BQP $\neq$ NP?

Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
1 vote