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.

4
votes
0answers
66 views

$\exists \mathbb R$ and IP

We know NP$\subset\exists \mathbb R\subset$ PSPACE=IP, but is there some more direct proof for $\exists \mathbb R\subset$ IP? What about the other direction, are there some Arthur-Merlin games that ...
0
votes
0answers
65 views

Is there a pseudorandom NP complete problem? [on hold]

The subject line pretty much says it. Is there an NP complete problem which is pseudorandom? The exact notion of pseudorandomness I want to leave open to different possibilities, but I have in mind ...
1
vote
0answers
49 views

Minimum cut with nonlinear objective function

Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum. Let us generalize it the following way: let $f$ be a ...
3
votes
0answers
70 views

Counting quotient graphs, but not exactly

All graphs considered will be directed graphs $G=(V,E)$, with $E \subseteq V \times V$ (so possibly with self-loops). For $k \in \mathbb{N}_{\geq 1}$, I will write $[k]$ the set $\{1,\ldots,k\}$. A $k$...
-1
votes
0answers
17 views

Lateral gene transfer and the origins of Life and how can that be analyzed from a mathmatical perspective [closed]

Albeit the complexity of protein folding is most certainly a difficult problem to pose to a computer as I would expect....there are an ALMOST infinite number of folds I would imagine. Here is my ...
-2
votes
0answers
23 views

Multiobjective Mixed Integer Linear Programming

We know that the program $$\max a_1x_1+\dots+a_nx_n$$ $$AX\leq b$$ $$X=(x_1,\dots,x_n)^T\in\mathbb Z^m\times\mathbb R^r$$ where $n=m+r$ can be solved in $m^{O(m)}poly(r)$ time. What is the ...
0
votes
1answer
132 views

Does Hadwiger conjecture imply that NP = coNP?

(Disclaimer: I suspect the answer is no, but I fail to see why) Here is a nice picture by David Epstein (taken from Wikipedia) illustrating Hadwiger's conjecture: The point is that if in a given ...
2
votes
0answers
46 views

Complexity of comparing extended integer power towers

Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
1
vote
1answer
57 views

Complexity status of the Edge Deletion problem to bounded degree graphs

I'm interested in the complexity status of the following problem. Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$. Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality ...
3
votes
1answer
125 views

How small can extension complexity be?

In this article on extension complexity of regular polygons https://arxiv.org/pdf/1505.08031.pdf it is mentioned that extension complexity of $n$ regular polygons should be $\theta(\log n)$. This is ...
0
votes
0answers
106 views

Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$

Given a $\Sigma^p_2$-complete oracle (i.e., $\Sigma_2 \mathrm{SAT}$), I have a problem that requires to call this oracle polynomially many times and returns an integer. Essentially, this is a function ...
1
vote
0answers
67 views

Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, ...
4
votes
0answers
95 views

Arranging letters to make a word in a regular language

Fix a regular language $L$ on the alphabet $\{a, b\}$, and consider the following problem. I am given as input: some number $m \in \mathbb{N}$ of copies of the letter $a$, and some number $n \in \...
2
votes
0answers
67 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 ...
0
votes
0answers
46 views

Are there candidate cryptographic schemes with polynomial time separation?

$RSA$ and discrete logarithm are popular $PKE$ schemes that provide sub-exponential time guarantee of security with current mathematical knowhow. Are there candidate cryptographic schemes other than ...
3
votes
0answers
133 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 ...
3
votes
0answers
47 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 = \...
8
votes
0answers
95 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
75 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}=...
1
vote
0answers
34 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....
3
votes
0answers
138 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
174 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+\...
1
vote
2answers
101 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, ...
4
votes
0answers
67 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 \...
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
197 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 ...
10
votes
0answers
137 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{...
7
votes
1answer
223 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? ...
9
votes
1answer
241 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, ...
4
votes
1answer
85 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
143 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
141 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 ...
-2
votes
1answer
113 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
73 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
64 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
0answers
52 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 $...
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 : ...
3
votes
0answers
65 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
126 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
113 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 $\...
2
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
100 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 ...
10
votes
1answer
158 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}$...
5
votes
1answer
145 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$ ...
2
votes
2answers
137 views

Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?

S-T CONNECTEDNESS Input: a (undirected) graph $G=(V,E)$; $s,t \in V.$ Output: number of spanning subgraphs of $G$ in which there is a path from $s$ to $t$. S-T CONNECTEDNESS problem is known to be #...
-3
votes
2answers
160 views

Do Turing complete languages automatically have efficient algorithms [closed]

Every Turing complete programming language can describe an algorithm that sorts sequences. Is it also true that every Turing complete language can describe an algorithm that sorts sequences in $\...
14
votes
0answers
432 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, $\...
6
votes
2answers
304 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 ...