# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

606 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
843 views

### k-CNF ←→ k-DNF conversion to minimize errors

the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby ...
246 views

### The latest concerning Valiant-Vazirani

I'm wondering what the best method obtained for the Valiant-Vazirani theorem is. We can state the following criteria: (1) First and foremost, has anyone been able to derandomize it? (2) If not, ...
243 views

### Is $\mathrm{co}(\mathrm{NP}^A) = (\mathrm{coNP})^A$?

I believe $\mathrm{co}(\mathrm{NP}^A) = (\mathrm{coNP})^A$: By definition, $L \in (\mathrm{coNP})^A$ means there is a PTIME Turing machine $M$, allowed to make oracle calls to $A$, such that for any ...
244 views

### Data structures lower bounds on Turing machines

Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ? I guess that people are mostly interested in models with random access, but ...
151 views

### The relation between NP and IP(2pfa)

As far as I know, it is not known whether $\mathsf{NP} \subseteq \mathsf{IP(2pfa)}$, where $\mathsf{IP(2pfa)}$ is the class of languages having interactive proof systems with some two-way ...
322 views

### Citation request: Complexity of determining if a graph exists with a minor but no subgraph in set

I'm looking for a reference of the complexity of the following problem. Let our input $C$ be a finite set of graphs. Is there a graph $G$ such that: $G$ has a minor in $C$ $G$ has no subgraph in $C$?...
139 views

### Complexity of DTMC subsystems

A discrete-time Markov chain (DTMC) is a tuple $M=(S,s_{init},P)$ where $S$ is a finite set of states, $s_{init}\in S$ the initial state, and $P:S\times S\to[0,1]$ the one-step transition probability ...
658 views

### Approximation results for 3-partition

The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
292 views

### Find the maximum set whose subset sum is unique for every of its subset

We are given a set of $n$ positive integers. We assume all of them are bounded by a polynomial of $n$. We would like to find a subset $S$ of these $n$ numbers such that for any $T_1,T_2\subseteq S$, ...
321 views

### Oracle complexity classes and hardness under different notions of reduction

Let C be a complexity class, and let L be a language such that PC ⊆ PL. Then it’s natural (and easy to prove) that L is C-hard with respect to Cook reductions (polytime Turing reductions). This ...
165 views

### Distributions over circuits and N-to-N vs N-to-1 circuits

This is really a two part question, and they aren't necessarily related. First, my understanding of natural proof barriers is that they are based on the idea that a suitable distribution over small ...
171 views

### Has there been any development of complexity theory for other Turing degrees than 0?

(I'm not sure if this question is better suited for MathOverflow or here. I'll try here first, and move over to MO later if it appears to be more appropriate.) Complexity theory can be very broadly ...
144 views

### What research is being done in classical complexity theory?

As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
133 views

### Parsimonious Reduction from Unique-3SAT to NAE-3SAT

Using the result by Valiant and Vazirani, we know that Unique-3SAT (3SAT with a unique solution) is hard unless NP=RP. Also it is widely believed that the "Unique" version of any NP-complete problem ...
140 views

148 views

### Graceful labeling completion problems

A graceful labeling of a graph with $m$ edges is a labeling of its vertices with some subset of the integers between $0$ and $m$ inclusive, such that no two vertices share a label, and such that each ...
169 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 ...
200 views

### Does the existence of an RP-complete language imply P = RP?

(I'm not sure if this is research-level, but I couldn't find an answer to this question elsewhere) The question of whether there exists an RP-complete language seems to be open, but I guess we believe ...
96 views

198 views

### Easy interactive proofs for easy problems?

Motivation Consider some $L \subseteq \{0,1\}^*$. Suppose Alice gives Bob a machine or oracle $M$ that purportedly decides $L$. If Bob has only polynomial time in their disposal, then they cannot ...
152 views

### Complexity of finding primes in arithmetic progression

By the Green-Tao theorem the prime numbers contain arbitrarily long arithmetic progressions. What is the computational complexity of the search problem in which the input is a natural number k encoded ...
375 views

### About the recent" paper by Razborov in the Annals of Mathematics

Recently this paper on complexity theory was published at the Annals of Mathematics by Razborov, http://annals.math.princeton.edu/2015/181-2/p01. Curiously this seems to have been submitted to the ...
85 views

### Computational depth and p-time hard instances

After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic ...
217 views

### Testing Isomorphism of projective planes

Miller showed that isomorphism testing of projective planes can be done in $v^{O(\log \log v)}$. I would like to know whether Babai's techniques that led to the quasipolynomial time algorithm for GI ...
72 views

### Finding of dimension of algebraic varieties

I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf). Are ...