Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
3,092
questions
0
votes
0
answers
28
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 ...
-1
votes
0
answers
19
views
Big O of evaluating expression under RAM model
I have a CS theory problem and want to figure out the Big O of my algorithm. Let n be the input size.
In the algorithm, I pre-process up to n expressions and these expressions grow in length (i.e. ...
1
vote
0
answers
34
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. ...
- 821
4
votes
1
answer
84
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,680
2
votes
1
answer
128
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 ...
- 121
4
votes
0
answers
60
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,680
1
vote
2
answers
143
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
51
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
68
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
35
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
103
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
113
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 ...
5
votes
1
answer
124
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
126
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 ...
- 245
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