# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,637 questions
Filter by
Sorted by
Tagged with
14 views

### Matrix multiplication when one matrix is fixed

Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry One is allowed to pre-process this matrix as appropriate. Given another positive integer entried $B$...
14 views

### $BPP$ type algorithms with slightly more capability

A language $L$ is in $BPP$ if and only if there exists a polynomial $p$ and deterministic Turing machine $M$, such that $M$ runs for polynomial time on all inputs For all $x$ in $L$, the fraction of ...
13 views

295 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 203 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 147 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 104 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 283 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{...
588 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 ...
191 views

### Lower bound on pebbling numbers

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”. (...
96 views

### How to prove a general convex set is nonempty or empty in polynomial time?

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 ...
224 views

### 3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
183 views

### Nondeterminstic Linear Time vs Other Complexity Classes

Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?
617 views

### A game on several graphs

Consider the following game on a directed weighted graph $G$ with a chip at some node. All nodes of $G$ are marked by A or B. There are two players Alice and Bob. The goal of Alice (Bob) is to ...
85 views

### Complexity of existence of simple polygonalization with prescribed area?

This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
1k views

### On the sensitivity conjecture?

The recent establishment of the relation $bs(f)=O(s(f)^4)$ goes through Gotsman,Linial . Can the same approach get to $O(s(f)^2)$ or is there an essential limitation to the approach?
170 views

### Counting solutions to extended MSO formulas, and sampling — do these appear in the literature?

I am trying to determine if the literature contains various extensions of Courcelle's theorem. Since I haven't been able to find these in the literature, I guess that these are folklore results, or ...
116 views

### Sensitivity and Low-Degree Approximation under Non-Uniform Distribution

I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
150 views

### reference request for construction of expanders

I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson. Arora/Barak has a chapter on it, but i find it ...
79 views

### Is there any research on the complexity of producing given a problem description?

It is straightforward enough to analyze the complexity of a particular algorithm as a function of input size or other variables in terms of runtime or space used or whatever else. I am wondering if ...
102 views

### Separation of AM and SZK

Are any results on the separation of AM from SZK known (e.g. relativized separation, or a separation assuming one-way functions exist, etc.)?
325 views

### Hidden Constants in Complexity of Algorithms

For many problems, the algorithm with the best asymptotic complexity has a very large constant factor that is hidden by big O notation. This occurs in matrix multiplication, integer multiplication (...
152 views

### Possibility of hierarchy with $UP$ class?

I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The ...
There is a type of results in TCS usually called bootstrapping results. In general, it is of the form If proposition $A$ holds, then proposition $A'$ holds. where $A$ and $A'$ are propositions ...