Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
3,105
questions
0
votes
0
answers
8
views
Consequences of $\#P$ reducing to $FP$ with oracle access to a certain class
Consider the problem "Given two $NTM$s and an integer $q$ does the number of accepting paths modulo $q$ agree?".
Is this problem complete for any class? Note $q$ is part of input. So $C_=P$ ...
- 13.1k
6
votes
1
answer
603
views
Is there a problem known to have no fastest algorithm, up to polynomials?
Is there a problem where for all correct algorithms $A$, letting $T(n)$ be the runtime of $A$, there exists $\varepsilon > 0$ and a correct algorithm $A'$ running in time $T(n)\cdot n^{-\varepsilon}...
- 2,471
10
votes
1
answer
231
views
Halting problem with minimal Turing Machine as promised input
Consider the following Turing Machine A.
Input: Turing Machine M that recognizes some language L(M)
Output:
If M is minimal (i.e. its length is minimum among Turing Machines that recognize the same ...
- 109
4
votes
1
answer
145
views
A potentially novel complexity measure for sets of strings
Inspired partly by Scott Aaronson's post about the first law of complexodynamics, I've been thinking lately about how to quantify the "interesting" or "structured" complexity of a ...
- 140
2
votes
0
answers
32
views
Is PP non-adaptively random self reducible?
It is well known that $\mathsf{\#P}$ is non-adaptively random self-reducible, with the common proof given via the permanent. Feigenbaum and Fortnow showed that this implies $\mathsf{PP}$ is adaptively ...
- 61
0
votes
0
answers
37
views
Is the problem of maximizing the weight loss in a spanning tree with edge restoration NP-hard?
Given $G = (V, E, w)$, an undirected weighted graph, where $V$ is the set of vertices, $E$ is the set of edges, and $w: E \rightarrow \mathbb{R}^+$ is a function assigning positive real weights to the ...
- 51
3
votes
0
answers
105
views
Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?
Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?
It is easy to show that the relaxed version ($\mathsf{E} \subset \mathsf{NP}$ and $\mathsf{P}^{\mathsf{NP}} \...
- 271
5
votes
0
answers
228
views
How to prove following weighted forest problem is NP-hard?
I am studying the following weighted forest problem, which is an optimization problem in graph theory focused on finding optimal forest structures in robust scenarios. The problem is defined as ...
- 51
1
vote
1
answer
74
views
Norm in the definition of sampling computational complexity class SampP
This paper defines the class of sampling problems SampP (see Definition 11). It requires that the probability of the generated samples $C_x$ is close to the target probability $D_x$ within an error $\...
0
votes
0
answers
75
views
Witness for NL Computation
For any NP language, we usually describe the language as having a polynomial time TM M such that for yes instance x you can find a witness such that M(x, w) accepts and for no instance M will not ...
1
vote
0
answers
65
views
Complexity of single bit recovery version of Integer Factorization problem
Consider the integer factoring problem with exactly 2 prime factors $p.q=N$. Given $N$ find the prime factors $p$ and $q$. The problem is notoriously difficult (on classical computers) and is the ...
- 831
5
votes
0
answers
144
views
Is this class between BPP and PP?
In analogy to BPP, I define a class XYZ (maybe it already has a name) as follows. For every language $L$ in XYZ, there is an algorithm $M$, such that:
$M$ runs in polynomial time on the size of its ...
3
votes
1
answer
134
views
Given a directed graph with edge weights $0$ or $1$, is there a way to find an odd cycle in $\mathsf{NC}$?
Given a directed graph with edge weights $0$ or $1$, is there a way to find an odd weight cycle in $\mathsf{NC}$? I think the decision version is in $\mathsf{NC}$, but I am not sure about the search ...
- 43
0
votes
0
answers
33
views
Nonexistence of short integer program sequence which generates squares - II
Is there a way to show within a mixed integer linear program with constant number of integer variables, $poly(\log B)$ number of real variables and constraints of length $poly(\log B)$ (say length $\...
- 13.1k
0
votes
0
answers
37
views
Integration of analytic function
It is the continuation of the question:
Complexity of analytic functions and integrals.
Given an input integer $t$ and a sequence of analytic functions $f_n(\cdots(f_0(x))$, with parameters $t$ itself,...
- 13
4
votes
2
answers
138
views
Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?
It is known that many-tape Turing machines can be simulated by a one tape Turing machine with extra runtime costs. Furthermore, a single-tape Turing machine with a larger alphabet can be simulated by ...
- 41
1
vote
0
answers
36
views
Clause Density for guaranteed Easy (2, 3) SAT Cases
It is known that its NP-Complete to decide the satisfiability of 3-SAT instances in which every variable occurs four times.
Now given a (2, 3)-SAT instance where each clause has length 2 or 3. ...
- 831
4
votes
1
answer
108
views
Solving #SAT through TQBF
I'm not extremely proficient with counting complexity classes, but since #SAT is #P-complete, its decision version, let's call it #SAT(D) (is the number of solutions less than some $k$), is in PSPACE. ...
- 1,704
2
votes
1
answer
168
views
Complexity of 2-coloring with extra constraints
I am considering the following problem:
Given a graph $G=(V,E)$ with $|V|=4n$ vertices, can we color the vertices in two colors (red and blue) with
The usual constraint that two vertices connected by ...
- 123
4
votes
0
answers
68
views
EXPSPACE-complete optimization problems
This is similar to this question but specifically for optimization problems.
Which are some optimization problems that (have corresponding decision problems that) are EXPSPACE-complete?
- 1,704
1
vote
2
answers
153
views
Use of transitive closure in proof of NC hierarchy collapse
Im looking at the proof of $NC^{i} = NC^{i+1} \implies NC = NC^i,\,i\geq 1$ in page 10 of the following article: https://www.cs.uoregon.edu/Reports/TR-1986-001.pdf
I understand the general idea ...
- 11
3
votes
0
answers
55
views
Complexity of minimizing the index of a subgroup of the free group
Let $\Sigma$ be a finite alphabet and $G$ the free group generated by $\Sigma$. Let $W$ be a finite subset of $G$. (Represented as a list of formal expressions of the form $a_1^{\pm 1}\ldots a_n^{\pm ...
- 2,181
2
votes
1
answer
72
views
Hardness of the Metric TSP for the Maximum Metric
I know that it is not too difficult to construct a metric to show that the metric TSP is NP-hard. The typical example is (1,2)-TSP.
I also know that Papadimitriou has shown that Euclidean TSP is NP-...
- 63
1
vote
0
answers
38
views
On the Relationship Between Graph Isomorphism and Equivalence in ETL Workflow Dependency Graphs
Let $G = (V, E)$ and $G' = (V', E')$ be two DAGs representing dependency graphs of ETL workflows. Each node $v \in V$ (or $v' \in V'$) represents a task, which is a tuple $t_v = (q_v, d_v, s_v)$, ...
- 11
2
votes
1
answer
109
views
On the power of QMA(2)
I searched for references. But I could not find any. Is $EXP\subseteq QMA(2)$ known?
- 21
1
vote
0
answers
116
views
Efficient algorithm to construct simple polygon from non-crossing orthogonal line segments
Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
- 21.1k
5
votes
1
answer
125
views
How to prove that a problem is not smoothed-polynomial?
Many research works use Smoothed analysis to prove that some NP-hard problems can actually be solved efficiently in typical cases. A different notion with a similar goal is Generic-case complexity.
...
- 2,294
1
vote
1
answer
139
views
Where does a problem lie which is NP-hard but not QMA-hard?
I saw this complexity classes diagram in this quantum computing paper in NATURE.
Based on the standard assumption of $P\neq NP\neq QMA$, they also seem to have related the NP-hard and QMA-hard ...
- 295
0
votes
0
answers
79
views
Evidence extended GCD is in $TC^0$
Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes ...
- 13.1k
4
votes
1
answer
105
views
Smoothed analysis in the Turing machine model
Smoothed analysis is usually defined using real numbers: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it ...
- 2,294
0
votes
0
answers
131
views
$P^{\#P}$ complete problems
Are there any known $P^{\#P}$ complete problems?
The problem would have to be at least as hard as anything in the polynomial hierarchy, but perhaps not as hard as PSPACE
- 101
0
votes
0
answers
58
views
Non-linearly ordered hierarchy of classes between NP and NEXP
I'm interested in the hierarchy of complexity classes between NP and NEXP. I have asked before about this Hierarchy of classes between NP and NEXP and found that already the time hierarchy theorems ...
- 1,049
4
votes
1
answer
141
views
Constructing vector valued boolean circuits from boolean circuits
This is a reference request. I'm
interested in the compositional construction of small boolean circuits
for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow
\mathbb{B}^n$ for $n >...
- 11.5k
4
votes
1
answer
80
views
Reference request: finite field computation over the Word-RAM model
Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$.
Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and ...
- 686
6
votes
1
answer
309
views
How stringent is the peer review process of ECCC exactly?
Apologies for the soft question. ECCC (the Electronic Colloquium on Computational Complexity), on its website (ECCC), says it is a compromise between the negligible peer review of ArXiv and the long ...
- 369
0
votes
0
answers
65
views
Resolution lower bound for pigeonhole principle when placement clauses are shortened
Consider the standard CNF encoding of pigeonhole principle $PHP_{n}^{n+1}$:
$$ \text{Placement clauses: } x_{i,1} \lor x_{i,2} \lor \cdots \lor x_{i,n} \forall i \in [n+1] $$
$$ \text{Collision ...
- 91
0
votes
1
answer
136
views
Hierarchy of classes between NP and NEXP [closed]
Ladner's theorem shows that if $P$ is different from $NP$ then there are actually infinitely many complexity classes (for polynomial time reducibility) between the two.
I was wondering if this is also ...
- 1,049
2
votes
1
answer
92
views
Time Complexity of KnuthBendixCompletion Algorithm [closed]
I am currently studying the Knuth-Bendix completion algorithm and trying to understand the factors that contribute to its time complexity. This algorithm is used to transform a set of rewrite rules ...
- 21
6
votes
0
answers
134
views
Is there a known correlation between the Strong Exponential Time Hypothesis (SETH) and the existence of one-way functions?
It is known that (one-way functions exist $\implies$ $\textbf{P}\neq \textbf{NP}$) and as far as my knowledge goes, the converse is not known to be true. Are there any known results correlating $\...
- 369
6
votes
0
answers
147
views
Proof complexity of Sudoku
Let $P$ be a $N$x$N$ Sudoku puzzle
(assume $N=n^2$ for some $n\in \mathbb{N}$,
e.g. standard $9$x$9$ puzzle is $n=3$).
We can represent it in propositional logic as follows:
Variables
$p_{i,j,k}$: ...
- 21.7k
4
votes
1
answer
152
views
Intersection Non-Emptiness for Two-Way Finite Automata
We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way ...
- 43
5
votes
3
answers
216
views
Why is order/choice an issue for a logic for PTIME
As I'm reading on the question of a logic for PTIME and in particular about CPT and its variants, whilst things make sense and I follow along, I came to realise that I don't fundamentally understand ...
- 51
4
votes
0
answers
102
views
Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?
We know that $\mathsf{BPP}$ is in $\mathsf{\Sigma^P_2\cap \Pi^P_2}$ by Sipser-Lautemann, as this proof relativizes we can get $\mathsf{BPP^{NP} \subseteq \Sigma^P_3\cap \Pi^P_3}$, but are there any ...
- 61
0
votes
0
answers
91
views
Proof of coNE ⊆ NE/poly
I'm finding it hard proving that NE/poly contains coNE which is backed by Complexity Zoo. It states that we can use the proof for NEXP/poly containing coNEXP but the link to the reference paper ...
- 1
0
votes
0
answers
52
views
On a modular inverse graph construction
Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
- 13.1k
2
votes
0
answers
73
views
On mod $p$ constructions related to determinant
Given an $m\times m$ matrix $M\in\mathbb Z^{m\times m}$ and a prime $p$, is it possible to construct in $Logspace$ another matrix $t_1(M)$ whose determinant is guaranteed to be determinant $Det(t_1(M))...
- 13.1k
3
votes
0
answers
57
views
Hardness of deciding fractional chromatic number at most $k$
I want to find a reference for the following statement. Here, $\chi_f(G)$ denotes the fractional chromatic number of a graph $G$.
For every fixed $r>2$, deciding $\chi_f(G) \leq r$ for a given ...
- 31
3
votes
0
answers
66
views
Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?
I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and ...
- 31
2
votes
0
answers
91
views
Evidence for $\oplus P\subseteq\#P$ and barriers to proving it
Is there evidence that $\oplus P\subseteq\#P$ and evidence towards $\oplus P\not\subseteq\#P$ ? We know $\oplus P\subseteq FP^{\#P}$
What are some barriers to proving this inclusion $\oplus P\subseteq\...
- 13.1k
0
votes
0
answers
64
views
Why can't we just reduce from Bounded HALT to Bounded PCP?
We know that:
PCP is famously undecidable (as it can encode any DTM), but
Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and
Bounded-PCP (there is a matching ...
- 101