# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,698 questions
Filter by
Sorted by
Tagged with
168 views

### Problem in deterministic time $n^p$ and not lower

I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable). ...
145 views

### The complexity of the permanent of low rank matrices

I know that for an arbitrary $n \times n$ matrix, Ryser's algorithm can compute the permanent in $\mathcal{O}(2^n n^2)$ time. I'm interested in computing the permanent of $n \times n$ matrices of rank ...
68 views

### the shorstest cycle containing two given points

I am given a edge-weighted (multi)graph $G$ and two of its vertices, $u, v\in V(G)$. I want to find two edge-disjoint paths that connects $u$ and $v$ while minimizing the sum of the lengths of the ...
99 views

### Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given $k$-clique cover. Let $G$ be connected simple graph. $k$-clique cover of graph $G$ is partition ...
2k views

### “Almost all objects have property P” vs. “It is easy to test whether an object has property P”

I am interested in any relation between "almost all objects(from a universe) possessing a particular property P" versus "testing whether an object has property P being poly. time decidable". My guess ...
98 views

### Is the counting version of 1-in-3 Sat #P-complete?

In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat. Cubic Planar Positive 1-in-...
47 views

### Randomized Reduction for Maximization Problem

I have two maximization problems $P_1$ and $P_2$ where the decision version $L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$ of $P_1$ is $\mathsf{NP}$-complete. Let $f:P_1\to P_2$ be a randomized ...
232 views

### Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?

This is another attempt to formalize my former question on the topic. I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (...
196 views

### Does two-sided error have more capability than one-sided error?

From $P=RP$ extrapolation we might think $EXP=REXP$. What evidence do we have $BPP\subseteq REXP$? What consequence $REXP\subseteq BPP$ gives other than what $EXP\subseteq BPP$ gives?
90 views

134 views

### The decision procedure of theory of closed real field is in NP-hard?

The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
50 views

### Maximum subgraph problem with unknown complexity

Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem: Maximum $Q$-...
163 views

### What is the complexity of checking equivalence of two boolean formulae without NOT symbol?

Suppose I have two boolean formulae (propositions) $P_1$, and $P_2$ (can be assumed to be in CNF) over the same variables and such that there are no "NOT" symbols used. I.e. only conjunction and ...
115 views

308 views

Consider the following problem: for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation define is it true that for every $S \subseteq \{1, ..., 2n \}$ such that $|... 0answers 207 views ### Conditional separations of$\exists\mathbb{R}$from$\mathbf{PSPACE}$As pointed out explicitly by Emil Jeřábek here: Even with Turing reductions,$\mathbf{PSPACE}=\mathbf{P}^{\exists\mathbb{R}}$would still be a breakthrough (and completely unexpected) result. So ... 1answer 160 views ### Evidence integer multiplication is in linear time? After millenia of quest we have identified two$n$bit integers can be multiplied in$O(n\log n)$time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-... 0answers 44 views ### Volume computation of special polytopes I'm interested in computing the volume of a special class of$\mathcal{H}$-polytopes and the complexity of doing so. I know that in general it is #P-hard to compute the volume of$\mathcal{H}$-... 1answer 134 views ### Satisfiability problems with restricted (not bounded) number of occurrences per variable Intro It is known that SAT is hard even when restricted to, e.g., formulas with exactly 3 literals per clause and at most 4 occurrences per variable. On the other hand it is easy if there are exactly ... 3answers 5k views ### Evidence that matrix multiplication is not in$O(n^2\log^kn)$time It is commonly believed that for all$\epsilon > 0$, it is possible to multiply two$n \times n$matrices in$O(n^{2 + \epsilon})$time. Some discussion is here. I have asked some people who are ... 1answer 300 views ### Evidence for$\mathsf{P} \neq \mathsf{PP}$if the polynomial hierarchy collapses? We think that$\mathsf{PH}$does not collapse, and that$\mathsf{PP}$is not in$\mathsf{P}$. Suppose on the contrary that$\mathsf{PH}$does collapse, say even$\mathsf{P}= \mathsf{NP}$.$\mathsf{...
744 views

Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
Out of curiosity, I tried finding the original paper showing that there are graphs that require $n/\log n$ pebbles in the sense of Hopcroft, Paul, and Valiant’s seminal paper “On Time Versus Space”. (...
The general convex set should be represented by a set of (generalized) inequalities $f_{i}(x)\leq 0$ with $f_{i}(x)$ being convex in $x$. I know ellipsoid method and interior method, but I do ...