# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,819 questions
Filter by
Sorted by
Tagged with
949 views

### Approximate counting problem capturing BQP

In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say). Is ...
3k views

### Monotone-2SAT and Vertex Cover

The following decision problem is called k-True-Monotone-2SAT: Given a 2-CNF boolean formula $F$ that does not contain any negated variables and given a positive integer $k$, can $F$ be satisfied ...
788 views

### LogDCFL-complete problems

LogCFL is the set of all languages that are logspace reducible to a context-free language. Similarly, LogDCFL is the set of all languages that are logspace reducible to a deterministic context-free ...
2k views

### Problems that can be used to show polynomial-time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
482 views

### Complexity of two perfect matchings with minimum shared edges?

Perfect Matching problem is polynomial time solvable in general graphs. Given undirected simple graph, Is the problem of finding two perfect matching with minimum shared edges between them ...
301 views

### On Defining Probabilistic/Nondeterministic Circuits

Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit. The standard way of defining probabilistic/nondeterministic circuits ...
453 views

### Do people look at loop nestness in boolean circuits?

While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought ...
2k views

### Reducing #SAT to #MONOTONE-2SAT

The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its ...
1k views

### Removing all but a few cycles in a graph

Let problem $S$ be defined as Given undirected graph $G$ and a set of cycles $C_1,C_2, \ldots, C_n$ in G, find minimum number of vertices that need to be deleted to remove all cycles in the ...
451 views

### Visualizing Unique Games

How would you design a picture to illustrate the unique games conjecture? This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be ...
3k views

### Semantic vs. Syntactic Complexity Classes

In his "Computational Complexity" book, Papadimitriou writes: RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
4k views

### Optimal greedy algorithms for NP-hard problems

Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
8k views

### NP-hard problems on trees

Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
1k views

### NP-complete variants of undecidable problems?

Examples of bounded $NP$-complete variants of undecidable sets: Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps} Bounded Tiling={ $(T, 1^t)$| there is ...
435 views

### Is this problem mappable to 3SAT or is it weaker than 3SAT?

Consider a variant of a satisifiability problem. Given n dimensions (n >= 3, n < 10,000 think of n as large but finite) The range of each dimension is either an interval over the integers or an ...