# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

590 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
145 views

### Recognition problem of cycle permutation graphs

A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, ...
165 views

### Problems in dynamic algorithms in computational geometry

The publication of Chiang and Tamassia's paper on dynamic algorithms in computational geometry included several algorithms used in solving dynamic computational geometry problems such as: Dynamic ...
245 views

### Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$ where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), ...
75 views

### How many exponentiations can the Shamir algorithm reduce?

The Shamir's algorithm is depicted as follows (cited from Handbook of Applied Cryptography, chapter 14, algorithm 14.88, page 618) Shamir's algorithm INPUT: group elements $g_0,g_1,\dots, g_{k-1}$ ...
126 views

### Complexity of edge coloring graphs with $\Delta(G) \ge n/3$

Let $C$ be the class of graphs satisfying $\Delta(G) \ge n/3$, where $\Delta(G)$ is the maximum degree of a graph $G$, and $n$ denotes the number of vertices. What is the complexity of edge coloring ...
240 views

### Notion of associativity for ternary relations?

Consider the problem $\def\GEN{\mathrm{GEN}}\GEN$: given a ternary relation $R \subseteq X^3$ and a subset $S \subseteq X$, is the closure of $S$ with respect to $R$ equal to the whole set $X$? By ...
114 views

382 views

### The number of maximal subsets with sum less than $m$

I've met this problem. I would like to know to which complexity class it belongs. Input a set of positive integers $I$, an integer $m$, an integer $n$. Question Is the number of $S \subseteq I$ ...
149 views

### Vertex Covers whose vertex induced subgraph has an even number of edges and no isolated vertices

Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties: Their corresponding vertex induced subgraph has an even number of edges. ...
269 views

### What does “no integrality gap” imply?

I'm currently working on a linear time heuristic for the rectangle decomposition of a binary matrix. This problem has a polynomial time solution, which in our case is too slow for large-scale ...
95 views

### What is the query and randomness complexity for very efficient PCPs?

In the 2012 paper On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs, the authors state the following (paraphrased from page 11). Theorem 1 (informal). There is a PCP system ...
552 views

### Nondeterministic linear time vs. the deterministic time hierarchy

How much is known about nondeterministic linear time? I'm aware that $$\mathrm{NTIME}(n) \neq \mathrm{DTIME}(n).$$ Is there an $m > 1$ so that $\mathrm{NTIME}(n) \not\subset \mathrm{DTIME}(n^m)$? ...
223 views

327 views

256 views

### Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two

It is well-known that different variants of Multicommodity flow problem are NP-complete. What is the complexity of the following variant, that is, the integral k-multicommodity flow problem with ...
271 views

### What is the complexity of #satisfiable instances of k-SAT ?

To continue the question posted by user1749 on Oct 13 2010 : How many instances of 3-SAT are satisfiable? Which was: Consider the 3-SAT problem on n variables. The number of possible distinct ...
207 views

### Complexity of Max Bisection on cubic planar graphs?

Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximum. Max Bisection is $NP$-complete on cubic graphs and also on planar ...
282 views

### Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

$CFL$ is the class of context-free languages. Question Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $DCFL$?
65 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 ...