Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

12
votes
1answer
1k views

Entropy and computational complexity

There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, ...
5
votes
2answers
224 views

Efficient way to generate random planar cubic bipartite graphs

3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to ...
9
votes
1answer
362 views

Is abelian group isomorphism in $\mathsf{AC^0}$?

An $O(n^2)$ running time algorithm for abelian group isomorphism is easy to see. Later working on this problem in 2003 Vikas improve the result from $O(n^2)$ running time to $O(n \log n)$. In 2007, ...
4
votes
0answers
67 views

Computational Complexity of the Helpmate problem in Chess

It is well known that Chess is EXPTIME-Complete. I am interested in the related "Helpmate" problem. Given an $N$ by $N$ chessboard, is there any sequence of at most $k$ moves that leads to Black's ...
3
votes
1answer
204 views

How to compute GCD efficiently?

I want to compute $ A= \langle \text{GCD}(a,j),j=2,3,..,k-1\rangle$ and assume that each value of $j$ is less than $a$. I can compute GCD(a,j), $j=2,3,..,k-1$ and $a \le j$ for single fixed value of $...
5
votes
0answers
89 views

Is $\mathrm{DTISP}(n^a,n^b) \subseteq \mathrm{DSPACE}(n^{b/2})$?

The title question arose in the course of discussing a question on MathOverflow. Obviously, from the space hierarchy theorem we know that not only is it false that $\mathrm{DSPACE}(n^b) \subseteq \...
-5
votes
1answer
128 views

Should GCT focus on $PSPACE\not\subseteq P/poly$?

GCT tries to show $P$ is not $NP$ by showing $NP$ is not in $P/poly$. Could it be useful in showing $\Sigma_{i+1}\not\subseteq P^{\Sigma_i}/Poly$ at every $i>0$? Suppose if it turns out that $\...
11
votes
1answer
205 views

Does the space hierarchy theorem generalize to non-uniform computation?

General Question Does the space hierarchy theorem generalize to non-uniform computation? Here are a few more specific questions: Is $L/poly \subsetneq PSPACE/poly$? For all space ...
4
votes
1answer
214 views

What is the complexity of counting parse trees?

A Counting Problem Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$? An Example Instance Let's consider an example instance consisting of a CFG $G$ with ...
1
vote
0answers
44 views

What is the best known gap between ZPP and Deterministic communication complexity? [duplicate]

I know that $N(f) \times coN(f) \geq D(f)$. This means that $ZPP(f) \geq \sqrt{D(f)}$. Is this separation tight?
10
votes
1answer
134 views

On sparse complete sets and P vs L

Mahaney's Theorem tells us that if there is a sparse $NP$-complete set under polynomial-time many-one reductions, then $P = NP$. (See "Sparse complete sets for NP: Solution of a conjecture of Berman ...
14
votes
1answer
186 views

What are the consequences of $P \subseteq L/poly$?

A language is in $L/poly$ if there exists a logspace Turing machine that decides the language with polynomial amount of advice. See here for more info: https://en.wikipedia.org/wiki/L/poly ...
7
votes
1answer
335 views

How to contribute incrementally to Theoretical CS - similar to github

I have been through all the basic undergrad classes in CS. I have finished a masters in CS. I have learned a decent amount about applying Haskell to engineering. I haven't studied abstract math yet. I ...
4
votes
1answer
232 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$?
1
vote
0answers
63 views

Relating classes of computational complexity to finding solution to classes of algebraic equations [closed]

Having related classes of computational complexity to finding solution to classes of algebraic equations, we may relate classes of computational complexity to algebraic geometry or complex geometry,...
5
votes
1answer
170 views

Verifying that a reduction is correct

Alice has a function $f: \{0,1\}^* \to \{0,1\}^*$ which can be computed in polynomial time. She claims that $x \in \mathrm{SAT} \iff f(x) \in \mathrm{CLIQUE}$. Alice sends the circuit computing $f$ on ...
3
votes
1answer
100 views

Complexity of maximising weighted sum of and functions on a set of binary variables

Suppose we have a set of binary variables $a_1, ..., a_n$ that $a_i\in\{0,1\}$. Now we define $m$ and functions over a subset of them: $$j\in\{1,...,m\}: f_j=x_1\land x_2\land...\land x_k$$ in which ...
4
votes
0answers
178 views

Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

To the best of my knowledge, it is known that $NEXP^{NP} \nsubseteq P/poly$, but it's still not known if $NEXP \nsubseteq P/poly$. For more info, see "Superpolynomial circuits, almost sparse oracles ...
12
votes
1answer
697 views

Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

In the recent preprint https://arxiv.org/abs/1801.00776, it is claimed that $n$ real numbers can be sorted in time $$O(n \sqrt{\log n}), $$ and linear space. The paper seems reasonable, though I am ...
7
votes
1answer
127 views

Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?

My understanding of the Presburger arithmetic decision problem is that it requires doubly-exponential time, but only singly-exponential space, meaning that it is in $EXPSPACE \setminus EXP$. ...
2
votes
0answers
165 views

Is Non-linear Constrained Optimal Exact Cover NP-Hard?

Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard....
17
votes
2answers
478 views

Is it possible to encrypt a CNF?

Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that The function $\Psi$ can be computed in polynomial time from some secret random parameter $r$. $\Psi(\mathcal ...
2
votes
0answers
61 views

On reduction between two classes?

https://link.springer.com/article/10.1007/s00153-013-0351-x gives seven reductions $m,c,d,p,btt(1),\ell,tt$. What does norm $1$ mean in $btt(1)$? Is there illustrative examples that help understand ...
20
votes
2answers
1k views

Can any computational challenge be transformed to proof-of-work?

The seemingly pointlessness of cryptocurrency mining raised the question of useful alternatives, see these questions on Bitcoin, CST, MO. I wonder whether there exists an algorithm that can convert ...
2
votes
1answer
111 views

What is conjunctive truth table reduction?

What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?
6
votes
0answers
285 views

Is there any algorithm outputing $e$ in real time?

The Hartmanis-Stearns Conjecture says that a number computed in real time by a Turing Machine is either rational or transcendental. We know that there is some transcendental (Liouville) number that ...
3
votes
1answer
126 views

Literature reference for search-BPP

I'm trying to find the first article/paper that the complexity class search-BPP appeared in. Search-BPP, as defined as follows (in [1]): A binary relation $R$ is in search-BPP if there is a ...
5
votes
1answer
94 views

Is $UP\not=NP$ with respect to random oracle?

It is shown in An average-case depth hierarchy theorem for Boolean circuits a random oracle makes $PH$ infinite. Is it possible to also show $UP\not=NP\not=\Sigma_2^P\not=\Sigma_3^P\not=\Sigma_4^P\...
0
votes
0answers
149 views

On $i.o.P/poly$?

Is $NEXP^{NP}\not\subseteq i.o.P/poly$? Is there any consequence if $NP$ or $PP$ is in $i.o.P/poly$? Showing $NEXP^{NP}\not\subseteq P/poly$ needs Karp-Lipton. What is the best $i.o.P/poly$ ...
1
vote
1answer
66 views

Recursively presenting or even enumerating all P-hard languages

A class of languages $C$ is recursively presentable if there is an effective enumeration of Turing machines $\mathcal{M}_1,\mathcal{M}_2,\ldots$ such that $C=\{L(\mathcal{M}_i)\mid i=1,2,\ldots\}$. ...
4
votes
0answers
149 views

Is Normal centralizer problem in P? [closed]

Notations $\le$ is used for subgroup $G = \langle A \rangle $ means group $G$ is generated by set $A$ $P$ means polynomial time in input size. $\Omega = \{1,2,3,\cdots,n\}$ is a input domain Sym($\...
4
votes
2answers
244 views

On $NP$, $\oplus P$ and $PP$?

We know $\oplus P^{\oplus P}=\oplus P$, $PP^{\oplus P}\subseteq P^{PP}$ and $NP\subseteq PP$. Is $\oplus P^{PP}=PP$? Why is it difficult to show $NP^{NP}\subseteq PP$? What is the smallest known ...
14
votes
1answer
695 views

Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold n, does A accept a word containing at most n distinct letters? (By k different ...
3
votes
1answer
82 views

How fine-grained can the time hierarchy theorem be in a reasonable model?

One version of the sharp or additive space hierarchy theorem is that for Turing machines (and a number of other deterministic sequential computational models) $\mathrm{Space}(f-ω(\log(n+f))) ⊊ \mathrm{...
1
vote
1answer
147 views

Proof of Majority is stablest in “reverse” in the MAXCUT hardness paper by Khot et al

This is about Proposition 7.4 here. I think there is a slight error in the proof of this proposition. Basically, authors have taken $g$ to be the odd part of the function $f$. Due to which we can say ...
3
votes
2answers
282 views

NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
9
votes
5answers
642 views

Can neural networks be used to devise algorithms?

After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I ...
12
votes
1answer
280 views

Is there a P-complete problem on diophantine equations?

In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem. I believe that deciding if a quadratic diophantine equation has any solution is NP-...
3
votes
0answers
168 views

Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds. What are the best statements we have proved that come close to ...
1
vote
0answers
141 views

Convention for RAM machine models

When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used? My understanding is that most problems use unit-cost ...
3
votes
2answers
161 views

Reduction of graph chromatic number to hypergraph 2-colorability

I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this ...
7
votes
2answers
231 views

Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

I am trying to find results on the best known time complexity for finding $(1+\epsilon) \log n$ sized cliques in $G(n,1/2)$. More general results would be great, i.e. if $C_p$ is the constant such ...
28
votes
0answers
670 views

Is BPP= P known for ANY uniform model of computation?

Many believe that BPP $=$ P "should" hold for Turing machines. We even have some "witnesses" for this: otherwise some "strange" things would happen; see e.g. this paper by Implagliazzo and Wigderson. ...
8
votes
4answers
451 views

Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

In Computability, if we want to prove that a problem is not recursive or not recursively enumerable, we can use e.g. reductions from other non-recursive or non-r.e. problems, Rice's theorem, Rice-...
-1
votes
1answer
132 views

Two queries related to Toda

Is the Isolation lemma crucial for $PH\subseteq BPP^{\oplus P}$ theorem and would avoiding the Isolation lemma say anything more that is not known?
2
votes
1answer
444 views

Does there exist an ontology for algorithms?

It appears that algorithmic complexity theory has already figured out Kolmogorov complexity, when applied to representations of programs themselves, can already serve as a solid theoretical metric of ...
18
votes
1answer
481 views

Formally Verified Complexity Theory

Is there any ongoing project to formally verify the theorems and proofs of complexity theory using a proof assistant like Coq? Are there any boundaries to doing this?
1
vote
2answers
154 views

Complexity of a variant of partition problem

Motivated by this post, Strongly NP-complete variants of subset sum or partition problem, I am interested in this variant of partition: Given a solution to balanced partition problem (both parts have ...
4
votes
0answers
172 views

What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$

We know that Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable,so what is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$? Is it equivalent to Tarski elimination ...
1
vote
0answers
58 views

On collapsing the Exponential time hierarchy

Define $\Sigma^E_0 = \Pi^E_0=E$, for every $n>0$, define $\Sigma^E_n=NE^{\Sigma^p_{n-1}}$, for every $n>0$, define $\Pi^E_n=CoNE^{\Sigma^p_{n-1}}$. Define the Exponential time hierarchy by $EH=\...