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.

1
vote
0answers
80 views

Testing emptiness property complexity in Sum of Squares Proof systems

Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where $$h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb ...
14
votes
1answer
246 views

Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

Preamble. The complexity class AM are those problems which can be solved by a two-round interactive proof system between a prover "Merlin" and a verifier "Arthur". A problem — which tests some ...
2
votes
0answers
33 views

how is time complexity defined in computational learning theory

In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$. Now ...
8
votes
0answers
83 views

Can we define a meaningful concept of exptime reductions (as opposed to polytime reductions) for classes like NEXP or NEEXP?

Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP-problem to another. However, if we consider larger complexity classes such as ...
1
vote
0answers
68 views

Complexity of planted root of a system of quadratic homogeneous polynomials?

Given homogeneous degree $2$ randomly chosen polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system $f_1=\dots=f_{m}=...
2
votes
0answers
39 views

Complexity of #PP2DNF where we also count on the number of clauses

The #PP2DNF problem is the following: we have variables $X = \{x_1, \ldots, x_n\}$, $Y = \{y_1, \ldots, y_n\}$, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form $\phi = \...
1
vote
0answers
32 views

Problems rephrased as quadratic unconstrained binary optimization

I was impressed when i came across Quadratic unconstrained binary optimization (QUBO) recently, and saw how one can rephrase many combinatorial problems into questions about optima of binary functions....
7
votes
4answers
391 views

In-approximability results in severely restricted graph classes

Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path $\notin APX$ unless $P=NP$). I don't know if it remains in-approximable in ...
1
vote
1answer
110 views

Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs. If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane ...
4
votes
6answers
397 views

Is there a linear space lower bound for streaming set equality?

Consider two streams. In each stream one string arrives at a time. A query asks: Is the set of strings that has arrived so far the same in both streams? Is there a linear space randomized lower ...
3
votes
0answers
131 views

Take a NEXP-complete problem and then have the input in unary. Why is this not NP-complete?

It is known that if any unary language is NP-complete, then P=NP. Suppose we take a NEXP-complete language with input $x$ in binary and witness $y\in\{0,1\}^{2^{poly(|x|)}}$ such that the verifying ...
11
votes
0answers
170 views

Computational Complexity of the Frobenius Problem

The Frobenius problem takes as input $n$ positive integers $a_1,\ldots,a_n$ with $\gcd(a_1,\ldots,a_n)=1$ and asks for the largest integer $F$ that cannot be written in the form $F=a_1x_1+a_2x_2+\...
28
votes
1answer
1k views

Functions that are Not Efficiently Computable but Learnable

We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable"...
1
vote
2answers
96 views

When is a problem specified on a TM contained in non-uniform classes such as P/poly? [closed]

In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, ...
-1
votes
0answers
121 views

$BPP$ before Adleman-Sipser-Gacs theorem?

Where was $BPP$ before it was in second level? If we show $BPP$ is in $P^{NP}$ then we would've separated $BPP$ from $EXP^{NP}$. What did $BPP$ in second level accomplish? Did it have to cross any ...
4
votes
0answers
66 views

Refinement of the hierarchy theorem of a complexity class

Say $\mathrm{CTIME}$ is some complexity measure, syntactic or semantic (e.g. $\mathrm{DTIME}$ or $\mathrm{BPTIME}$). If we already know that for some $f(n) = \omega(n)$, $\mathrm{CTIME}(n) \subsetneq \...
13
votes
2answers
1k views

Is ALogTime != PH hard to prove (and unknown)?

Lance Fortnow recently claimed that proving L != NP should be easier than proving P != NP: Separate NP from Logarithmic space. I gave four approaches in a pre-blog 2001 survey on diagonalization ...
0
votes
1answer
65 views

Question on deduction that a certain problem requires exponential space

My question concern's a statement from the classic paper The equivalence problem for regular expressions with squaring requires exponential space. Regular expressions with squaring are like ordinary ...
8
votes
1answer
191 views

Depth reduction for Boolean circuits

This result by Tavenas, Koiran and others show that any polynomial computed by a circuit of size $s$ is computed by a depth-4 homogenous circuit of size $s^{\sqrt{d}}$. Are there any similar results ...
6
votes
1answer
217 views

Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)

In the wikipedia article on Time Complexity it is written that: The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, ...
1
vote
0answers
240 views

On $BPP$ in $P^{NP}$ and $SETH$

It is believed showing $BPP$ in $P$ involves good $PRG$s and faces lower bound barriers. Does showing $BPP$ in $P^{NP}$ which would mean $BPP\neq EXP^{NP}$ face similar $PRG$ and give lower bounds? ...
14
votes
4answers
2k views

Counting the number of vertex covers: when is it hard?

Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$. I'd like to know if there is any result showing how the hardness of such problem varies with ...
10
votes
0answers
134 views

A proof of measure 1 oracle separation of $\mathbf{NP}$ and $\mathbf{PCP}(O(\log{n}), O(1))$

I came across Theorem 2 of the following paper https://www.csee.umbc.edu/~chang/papers/revisionist/rev-book.pdf by Hartmanis et. al. It states that: With probability 1, $\mathbf{NP}^A\neq \mathbf{...
-1
votes
0answers
112 views

Can UNAE3SAT be converted into a P-complete decision problem?

By Self-reducibility, we understand that a search problem can be reduced to the same problem but by a decision problem instead of a function problem. P is trivially self-reducible, but what about P-...
12
votes
2answers
458 views

Does PPAD really capture the notion of finding another unbalanced vertex?

Complexity class PPAD was invented by Christos Papadimitriou in his seminal 1994 paper. The class is designed to capture the complexity of search problems where the existence of a solution is ...
64
votes
7answers
3k views

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD). Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a ...
7
votes
0answers
114 views

Can relativization technique be applied to natural NP-complete languages?

Levin [1] defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is ...
12
votes
3answers
858 views

Edge-partitioning cubic graphs into claws and paths

Again an edge-partitioning problem whose complexity I'm curious about, motivated by a previous question of mine. Input: a cubic graph $G=(V,E)$ Question: is there a partition of $E$ into $E_1, E_2, \...
9
votes
1answer
233 views

What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?

A weaker form of Gödel's First Incompleteness Theorem, direct proofs of which in Gödel's manner are lengthy, involved and at some place rather counter-intuitive, has a simple and intuitive proof based ...
0
votes
0answers
67 views

Where is the flaw in this proof that an LP solves TSP? [duplicate]

In this preprint on Arxiv, M. Diaby, M.H. Karwan, and L. Sun give a Linear Program which they claim solves the Traveling Salesman Problem. In contrast to their prior work, which was asked about here, ...
2
votes
1answer
77 views

Computational hardness for sampling a uniform matching

A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one ...
6
votes
0answers
138 views

Can reciprocal inputs speed up monotone computations?

A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\...
2
votes
1answer
138 views

An equation relating Time complexity, Space complexity, and entropy of output

Is there an equation that relates minimum time complexity, minimum space complexity, and entropy of the output of a function? It seems to me that there should be a relatively intuitive relationship ...
5
votes
2answers
297 views

Is this partition problem strongly NP-complete?

Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ...
-2
votes
1answer
107 views

Does P^NP=NP imply NP=coNP? [closed]

If you have it, the proof would be appreciated. Note: P^NP means P with NP oracle
2
votes
0answers
71 views

Best algorithms for real linear programming

Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of ...
2
votes
0answers
61 views

Complexity of counting Wang tiles

Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?
2
votes
1answer
59 views

Weighted Min-Cut in bounded-genus graphs

What is the status of the following decision problem ? Input : A graph $G=(V,E)$ embedded in a torus (or more generally a surface of genus $g$), a weight function $w:E \rightarrow \{-1,1\}$ Output : ...
2
votes
0answers
49 views

How to improve this pseudorandom generator?

Let $f$ be a Boolean function and $\varepsilon > 0$. There exists a pseudorandom generator $G_f: \{0,1 \}^{n^{\varepsilon}} \to \{0,1 \}^n$ with the following property. Let $T$ be a set and $...
5
votes
1answer
141 views

Viola's Reduction of 3XOR to listing triangles

Apparently this was due to Pătraşcu, but in this report on the ECCC server, Viola states that 3XOR can be reduced to listing triangles. Assume that given a graph in adjacency list format, with $m$ ...
3
votes
0answers
59 views

Is #PP2DNF hard to approximate?

The problem #PP2DNF asks to count the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula $\phi$ on variables $X_1, \ldots, X_n, Y_1, \ldots, Y_m$ of the ...
2
votes
1answer
124 views

Would an NP-complete public key cryptosystem imply NP=co-NP?

Would the existence of an NP-complete (or co-NP-complete) public key signature cryptosystem imply that NP = co-NP? My specialty is definitely not theoretical computer science, so this is somewhat of ...
5
votes
2answers
105 views

Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?

The only examples of $\sharp P_1$ complete problems I've seen are fairly abstract : e.g. here https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf Valiant proves that there exists a $\...
3
votes
0answers
54 views

Conjugacy testing problem

The below-given problem is in black box setting means input is given by set of generators. Given an abelian $p$-group $A$ and two matrices $U_1$ and $U_2$ in $R(A)$ such that the order of $U_1$ and $...
2
votes
0answers
94 views

Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?

I'm confused about how to prove either of the following closely related statements. They are both from this paper: https://epubs.siam.org/doi/10.1137/0208032 1) "A further problem that can be shown ...
9
votes
1answer
156 views

Natural candidates for NP-E and E-NP

It has been known since the early 70's that ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$...
13
votes
1answer
423 views

Is there a P-complete language X such that succinct-X is in P?

I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
13
votes
2answers
408 views

multi-party Communication complexity of “Set Partition problem”

In an application I'm considering, I need to know the communication complexity of the following problem: Given $n$, let $S$ be the set of integers from $1$ to $n$. Alice, Bob, and Carol each ...
44
votes
4answers
12k views

Approximation algorithms for Metric TSP

It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time. Is anything known about finding approximation solutions in ...
8
votes
3answers
697 views

One way randomised communication complexity of disjointness

I am looking for a reference for the (classical) one way randomised communication complexity of disjointness when the universe can be large. Say Alice and Bob both have sets of size $m$ chosen from a ...