Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
1
vote
1answer
61 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 ...
-1
votes
0answers
76 views
What kinds of algorithm have running time $O(\log n/ \log \log n)$in most of the cases? [closed]
I'm curious that what kinds of algorithm have running time $O(\log n/ \log \log n)$in most of the cases.
Since I'm working on a project that requires speedup for algorithms, I need general knowledge ...
-6
votes
0answers
46 views
who is able to solve that paper [closed]
Exams
Determine the time complexity of the following program statement in java
for (int i = 10; i < 20; i = i+ 1) {
for (int j= 10; j < 20; j = j + 1) {
Y=(a(i,j) ^2 )+5;
System.out....
1
vote
0answers
54 views
Complexity of enumerating over promise problems and circuits?
Given an enumeration over all Turing Machine which run with increasing length, is there a ``complexity class'' which describes the complexity of determining whether a given TM satisfies the promise ...
11
votes
0answers
112 views
Can two-tape read-only Turing machines recognize any recursive language?
Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes.
It cannot write on the tapes, but it can move on them in both ways, even move off from the input.
So for example, ...
11
votes
1answer
221 views
Is DSPACE(n) = DSPACE(1.5n)?
From space-hierarchy theorem it is known that if $f$ is space-constructible then
DSPACE($2f(n)$) is not equal to DSPACE($f(n))$.
Here, by DSPACE($f(n))$ I mean the class of all problems that can ...
1
vote
1answer
368 views
Possible to do Complexity theory with only counting and Pigeonhole
Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient ...
5
votes
1answer
230 views
Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?
A decade ago I observed what I dub "Murphy's Law of Complexity Theory": whenever a new separation or collapse is discovered, the question is answered in the direction that makes $P\overset?=NP$ most ...
-2
votes
1answer
113 views
Why $PSPACE!=Dtime(2^n)$? [closed]
Why $PSPACE != Dtime(2^n)$? I can not see how padding argument can help here, how can it be proven?
9
votes
1answer
125 views
Best known asymptotic PCP sizes / 3-SAT
What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am ...
10
votes
0answers
92 views
Complexity of checking $a > br^m + cr^n$, with $r$ rational
I'm wondering if the following problem is decidable in P-time (or even NP):
Given $a, b, c \in \mathbb{Z}$ and $m, n, p, q \in \mathbb{N}$ all in binary, decide if $a > br^m + cr^n$, where $r = {p ...
2
votes
1answer
95 views
Minimization version of matrix p-norms?
I considered a minimization version of matrix p-norms, defined for a matrix $A$ by
$$
f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.
$$
Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
1
vote
1answer
233 views
$P=BPP$ without good PRGs?
We know that the existence of good pseudorandom generators (PRGs) does not only imply $P=BPP$, but also $PromiseP=PromiseBPP$.
Let us assume $PromiseP\ne PromiseBPP$. Then good PRGs do not exist. ...
5
votes
1answer
103 views
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total ...
4
votes
1answer
62 views
Complexity of finding Exact Size Cut-Sets in Bipartite Graphs
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
9
votes
1answer
323 views
What is the complexity of this game?
This is a generalization of my previous question.
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after ...
5
votes
1answer
103 views
Counting/Enumerating Minimal Edge Covers
A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it.
Questions
Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial ...
11
votes
1answer
149 views
Linear circuit complexity classes
The class $\textrm{NC}^i$ is the class functions computable by circuits families of bounded fan-in, $n^{O(1)}$ size and $O(\log^i(n))$ depth.
The $\textrm{NC}$-hierarchy is the union of those classes....
3
votes
2answers
394 views
Is there a non-deterministic version of the complexity class PP?
From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)
Edit: Perhaps I ...
10
votes
1answer
212 views
Is algorithmic information theory still evolving?
I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory.
The field seems very interesting for me, but it seems everything is the field was done ...
8
votes
0answers
109 views
Complexity of fractional SAT
Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
9
votes
0answers
140 views
Relatively low ambitious frontiers
What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing?
For example: In the draft version of Arora ...
5
votes
1answer
175 views
Boolean circuits which correspond to L/poly
Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$.
Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\...
7
votes
0answers
167 views
How many different proofs are there of parity is not in AC0?
The theorem that Parity is not in $\mathsf{AC}^0$ is one of the gemstones of complexity theory. I wonder how many different proofs there are of this result? What constitutes "different" is also a part ...
8
votes
0answers
218 views
L/quasipoly vs NL/poly
Savitch's theorem shows that NSPACE($S(n)$) $\subseteq$ SPACE($S(n)^2$), which means that nondeterminism can be replaced by more spaces in this situation. Is it known whether nondeterminism can be ...
0
votes
0answers
33 views
How should a reduction to the Cardinality Constrained Quadratic Knapsack Problem work?
in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it.
Besides, it's easy to ...
7
votes
1answer
189 views
TIME(n) versus TIME(nlogn)
The time hierarchy theorem implies TIME($n$) is strictly contained in TIME($n\log^{1+ε}n$) for all ε>0. Is the relationship between TIME($n$) and TIME($nlogn$) known?
6
votes
0answers
91 views
Efficient quantum algorithm for CLASSICAL FFT
Is there a known improvement on the current O(n*log(n)) algorithm for CLASSICAL FFT using quantum computation? 'n' is the number of samples.
I need to find the amplitude and phase of the K dominating ...
3
votes
1answer
95 views
Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist?
Does there exist an algorithm, about which a non-constructive $\omega$-consistent theory $A$ can prove that it has time complexity $O(f(n))$ where $n$ is some univariate function of the input, but ...
7
votes
0answers
52 views
Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times
When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem:
Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,...
0
votes
0answers
61 views
Proving that a problem is coNP-complete [duplicate]
Let $\le^{p}_{T}$ be the Turing or the Cook reduction and $\le_{m}^{p}$ the Karp-Levin reduction.
I know that to prove a problem $P_1$ is coNP-complete I just need to show that $P_1 \in coNP$ and ...
5
votes
0answers
79 views
Parsimonious Reduction from Unique-3SAT to NAE-3SAT
Using the result by Valiant and Vazirani, we know that Unique-3SAT (3SAT with a unique solution) is hard unless NP=RP. Also it is widely believed that the "Unique" version of any NP-complete problem ...
1
vote
0answers
38 views
How to efficiently verify if a semantic symmetry of a CNF formula is valid?
It is easy to verify that a syntactic symmetry of a CNF formula is correct.
Is it also possible to check in polynomial time that a semantic symmetry which is not a syntactic symmetry of a formula is ...
8
votes
2answers
246 views
Non-Orthogonal Vectors Problem
Consider the following problems:
Orthogonal Vectors Problem
Input: A set $S$ of $n$ Boolean vectors each of length $d$.
Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
4
votes
3answers
121 views
Complexity of isotopy of embedded graphs
I am looking for previous work on the following problem: given two graphs embedded in the plane without crossing, determine if they are isotopic. By isotopic I mean that there is a continuous ...
4
votes
0answers
90 views
Asymptotic complexity of mass production
For a function $f:\{0,1\}^n \rightarrow \{0,1\}^m$, let $C(f)$ be the circuit complexity (for concreteness, constants and NOT gates are free, while 2-input AND gates cost 1).
Let $k{\times}f : \{0,1\}...
10
votes
1answer
197 views
Fast classical simulation of quantum algorithms
Are there examples of cases where the classical simulation of a quantum algorithm for a problem outperforms the best previously known classical algorithm for this problem? "Outperforms" doesn't have ...
1
vote
0answers
55 views
Reasoning about NP hardness of optimization problems with closed form functions as input
(This may not be a research level question per se. I can delete this question if the community thinks this way too)
I am trying to understand how to reason about hardness of optimization problems ...
10
votes
1answer
293 views
Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons
Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons?
Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem, but ...
0
votes
0answers
34 views
Minimum cost circulation problem with bounded number of edges
Note: the question was taken from https://cs.stackexchange.com/questions/95479/minimum-cost-circulation-problem-with-bounded-number-of-edges
Since there was no answer in that forum (even after ...
3
votes
1answer
190 views
Conesequences of $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$
Does $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$ has any separation of classes or consequences?
My main question is can use this to show that $P \neq NP$ or some thing useful ...
0
votes
0answers
52 views
Modular and multiplication operations
Does
modular operation reduce to integer multiplication
integer multiplication reduce to modular operation
in fully linear time and/or in logarithmic time on linear number of processors?
0
votes
1answer
46 views
Understanding the definition of a “restriction of a resolution derivation”
I am reading the paper An Introduction to Lower Bounds on Resolution Proof Systems. In its subsection 2.3 the author gives an inductive definition of the restriction of a resolution refutation $\pi$.
...
-2
votes
1answer
220 views
Why is it a mystery if PSPACE ?= EXPTIME?
It seems obvious to me that $PSPACE \neq EXPTIME$. I, however, do not believe that my seemingly obvious logic would not be picked up by more intelligent people if it was so simple, so I'm assuming ...
15
votes
0answers
409 views
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For ...
3
votes
1answer
65 views
NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?
It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: https://epubs.siam.org/doi/abs/10.1137/0205049
For a problem I'm ...
6
votes
1answer
136 views
Does there exist a polynomial time algorithm to determine whether an equation is a consequence of (x+y)*(y+z)=(x*y)+(y*z)?
Consider the identity $C$
$$(x+y)\times(y+z)=(x\times y)+(y\times z).$$
Is the problem of determining whether an identity is a consequence of $C$ in universal algebra a polynomial time problem? This ...
10
votes
1answer
238 views
Is this game EXPSPACE-complete?
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be ...
5
votes
1answer
93 views
Is Bayes optimal RL of a finite set of DFAs feasible?
Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta_k:Q\times\Sigma\rightarrow Q\}_{k=1}^n$ be a set ...
3
votes
0answers
51 views
Pseudodeterministically choosing elements from efficiently samplable distributions (or, the plausibility of a weak choice principle)
Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^...
