# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,650 questions
Filter by
Sorted by
Tagged with
31 views

### How does 3-SAT necessarily becoming greater-than-3-SAT not prove P != NP? [closed]

So I've done some messing around with 3SAT and I've found some people who have found some of the things I've found. For example: ...
39 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 ...
69 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 ...
70 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-...
34 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 ...
173 views
+100

### 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 (...
58 views

296 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 205 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 151 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 43 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 108 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 289 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{...
618 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 ...