Tagged Questions

Computational complexity classes and their relations

0answers
2 views

how to prove this unsolvable problem about halting problem (turing machine)

Show that the problem of deciding, for a given TM M, whether M halts for all inputs within n^2(namely n square ) steps(n is the length of the input) is unsolvable. You can use the fact without proof ...
1answer
89 views

Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$

It is known that some (non-relativized) syntactic complexity classes between ${\bf P}$ and ${\bf PSPACE}$ have the following property, \${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf ...
0answers
120 views

Is it known that $NEXP = \Sigma_2 \implies NEXP = MA$?

Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds? (The question is inspired by well-known \$\mathsf{NEXP} \subseteq \mathsf{P/poly} ...
1answer
166 views

On the proof of Meyer's Theorem

Meyer's theorem is one of the classical results about collapse of the polynomial hierarchy such as famous Karp Lipton's theorem, and states that \$EXP \subseteq P/poly \Rightarrow EXP = \Sigma_{2}^{p} ...
0answers
79 views

Is there a simpler proof of Beigel and Tarui's transformaion of ACC0 circuits

Beigel and Tarui's transformation of $\mathsf{ACC}^0$ circuits to depth 2 circuits with a polylog symmetric function on top is one of important results in the circuit complexity. For example, the ...
1answer
138 views

Consequences of OWFs for Complexity

It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question ...
0answers
64 views

Conditional Results on Bounded Depth Circuit Hierarchy

$\mathsf{AC,ACC,TC}$-hierarchy are basic bounded depth circuit hierarchies. $AC$-hierarchy is $\bigcup _{i =0}^{\infty} AC^{i}$ , where $AC^{i}$ is the $i$-th level of the hierarchy: a family of ...
0answers
89 views

TQBF $\notin$ SPACE($n^{1/3}$) [closed]

I want to show that TQBF $\notin$ SPACE($n^{1/3}$). Can I use the fact that TQBF is PSPACE-complete to show that there is a language L $\in$ SPACE(n) that reduces to TQBF in polynomial time, and ...
0answers
228 views

What is the complexity of this edge coloring problem?

Recently, I have encountered the following variant of edge coloring. Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying ...
0answers
29 views

Are all Integer Linear Programming problems NP-Hard? [migrated]

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
3answers
357 views

What is the fastest known simulation of BPP using Las Vegas algorithms?

$\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes. $\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the ...
1answer
146 views

How powerful are nondeterministic constant-depth circuits?

A nondeterministic circuit is a Boolean circuit that has nondeterministic input wires. In other words, a nondeterministic circuit $C$ computing a Boolean function \$f\colon\{0,1\}^{n}\rightarrow ...
2answers
192 views

Is Parity-P contained in PP?

This question was asked by Jan Pax on the Foundations of Mathematics mailing list. Certainly $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ but I suspect from the answers to this question that it's not ...
1answer
511 views

How can a problem be in NP, be NP-hard and not NP-complete?

For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP. However, in the famous paper "The ellipsoid method and its consequences in ...
2answers
387 views

Is adiabatic quantum computing as powerful as qubit computing?

Much of quantum computing literature focuses on qubit-based computation. Adiabatic quantum computing is not based on qubits. I am looking for insight into any of the following. Is adiabatic quantum ...
1answer
191 views

Smooth Complexity of the Nonnegative Permanent

There has been fantastic work done on the Permanent going on for the last two decades.I have been wondering for a while about the possibility of a Smooth P algorithm for the Permanent of Nonnegative ...
1answer
809 views
+50

About Inverse 3-SAT

Context: Kavvadias and Sideri have shown that the Inverse 3-SAT problem is coNP Complete: Given $\phi$ a set of models on $n$ variables, is there a 3-CNF formula such that $\phi$ is its exact set of ...
1answer
181 views

On $\mathcal L$, $\mathcal{N\!L}$, $\mathcal L^2$, $\mathcal P$ and $\mathcal{N\!P}$

We know that $\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}$. From Savitch's Theorem, $\mathcal{N\!L}\subseteq\mathcal{L}^2$, and, from Space Hierarchy Teorem, ...
2answers
435 views

P vs NP: Instructive example of when Brute Force search can be avoided

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
0answers
128 views

Big O notation for “modulo a polynomial”

Is there a notation that would be like the Big O notation (let's say Big P), but with the following definition: $f=P(g)$ if there exists a polynomial p such that for n large enough, $f\leq p(g(n))$? ...
0answers
46 views

Nonmetric TSP and Functional Compleixty Classes

Non-metric TSP that is TSP and some instance is not hold the triangle inequality is NP-hard by gap-reduction method. Is this general TSP a complete problem in some functional complexity classes ? ...
0answers
93 views

Smallest Nonuniform Complexity Classes including uniform-P

As we know, studiyng differences between uniform complexity and nonuniform complexity class is crucial. For example, P/poly is defined as challenges to derive a separation between P and NP, because ...
1answer
189 views

How do you argue a query is impossible in a query language like SPARQL or SQL?

I've been investigating the ability of the SPARQL query language to represent certain basic tasks in graph theory and machine learning, and have come to believe that it is not possible to do some. For ...
1answer
200 views

Computational Complexity of Computer Vision Problems

What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard? In most cases this will boil down to determining ...
1answer
304 views

Does every Turing-recognizable undecidable language have a NP-complete subset?

Does every Turing-recognizable undecidable language have a NP-complete subset? The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
0answers
92 views

Structural equivalence of two context-free grammars

I understand that determining if two context-free grammars are structurally equivalent is decidable (according to the 1968 paper by Paull, M.C. and Unger, S.H., "Structural equivalence of context-free ...
1answer
358 views

Consensus on P = NP in a world where RP = NP

$RP = NP$ is widely conjectured to be false. But imagine for a moment that it is true. In such case, how likely would be that $P = NP$? Put in other words: in a world where $RP = NP$, what might ...
0answers
113 views

Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER

The $\oplus$3-REGULAR BIPARTITE PLANAR VERTEX COVER problem consists in computing the parity of the number of vertex covers of a 3-regular bipartite planar graph. Question Which is the ...
1answer
243 views

How hard is to compute $\Delta_{|V|}$?

Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in this question. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds:  |\mathcal{C}| = 2^{|V|} - \sum_{k = ...
1answer
184 views

Is deterministic pseudorandomness possibly stronger than randomness in parallel?

Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a ...
3answers
539 views

Constructivity in Natural Proof and Geometric Complexity

Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$. Constructivity in Natural ...
0answers
84 views

Fullness of regular expressions with exponentiation

Meyer & Stockmeyer proved many years ago that the following problem is NEXPSPACE complete, called "fullness of regular expressions": Input: regular expression with exponentiation Output: true if ...
1answer
54 views

Natural relativized worlds

The oracles that are used in relativized collapses or separations of complexity classes rarely represent $natural$ algorithmic problems. They are typically constructed "artificially" with techniques ...
1answer
262 views

Computational complexities in factoring

[Note: n is a given integer (not the number of its digits)] I'd like to know how O(sqrt(n)/log(n)) would compare against the computational complexity of the best available algorithms (as well as the ...
3answers
598 views

Is NPI contained in P/poly?

It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then ...
1answer
113 views

Complexity results for Lower-Elementary Recursive Functions?

Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web. The elementary recursive functions ...
0answers
155 views

Narrowing the gap between BPP and RP

We do not know yet whether the 2-sided error of $BPP$ allows more computing power than the one sided error of $RP$. In view of derandomization results, the conjectured answer is no, since both classes ...
1answer
104 views

Complexity of Hidden Subgroup problems

Has anyone classified the (non-quantum) complexity of the hidden subgroup problem for finite Abelian groups? Is it known to be in any classical (not quantum) complexity classes?
1answer
110 views

Algebraic (or numeric) invariants of complexity classes

I hope this question isn't too naive for this site. In mathematics (topology, geometry, algebra) it is common for one to distinguish between two objects by coming up with an algebraic or numerical ...
2answers
323 views

What is $DTIME(n^a)^{DTIME(n^b)}$?

This might be embarrassing, but it turned out I don't know what is $DTIME(n^a)^{DTIME(n^b)}$. It is between $DTIME(n^{ab})$ and $DTIME(n^{a(b+1)})$ but where? Update: There are three possible ways to ...
1answer
138 views

Is semantic language complexity class UP Turing equivalent to syntactic language complexity class US?

${\sf UP}$ is defined in terms of unambiguous-SAT which asks if there exits at most one solution or no solution. On the other hand, ${\sf US}$ is defined in terms of unique-SAT which asks if there ...
1answer
76 views

Consequences of a $p$-optimal proof system for $\operatorname{TAUT}$

I'm reading a paper which shows the result: $(1)$ There is a $p$-optimal proof system for $\operatorname{TAUT}$. $\Leftrightarrow$ $(2)$ $L_{\leq}$ is a $P$-bounded logic for $P$. Both $(1)$ and ...
0answers
478 views

What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq$ $\mathsf{polyL}$, where \$\mathsf{L}^2 = ...
1answer
212 views

Counting reduction from #SAT to #HornSAT?

Is it possible to find a counting reduction from #SAT to #HornSAT? I haven't found this question posted here, so decided to check if anyone has any answer to this. Let me explain what do I mean by ...
1answer
320 views

What if a problem is both in $\Pi_2^p$ and $NP$-hard?

If a problem $P$ belongs to both $\Pi_2^p$ and $NP$-hard (thanks to some reduction from a $NP$-complete problem) but not to $NP$, does it imply that $P$ is $\Pi_2^p$-complete? If the answer is no, ...
1answer
106 views

Literature for restrictions that make NPC-Problems to P

The boolean satisfiability problem is in $\mathcal{NPC}$. But if you only get Horn clauses, it is in $\mathcal{P}$. I've already heard similar statements. Do you know a more general statement when ...
1answer
176 views

Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?
0answers
98 views

The power of randomized logspace with two-way access to the random tape

Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the ...
1answer
103 views

Two way deterministic multihead counter automata or logspace TM with counter

Is that known something about languages recognized by two-way deterministic multihead counter automaton or logspace TM with counter (equivalent model)? This class called Aux2DC in my advisor's paper. ...
0answers
155 views

Descriptive complexity characterization of TimeSpace classes

Are there descriptive complexity characterizations for TimeSpace complexity classes like $\mathsf{SC^i}= \mathsf{DTimeSpace}(n^{O(1)},O(\lg^i n))$?
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 91, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9108557105064392, "perplexity_flag": "middle"}