Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
0
votes
0answers
4 views
Does $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn})$ closed under polynomial reduction?
It's well known $EXP$ is closed under polynomial reduction. It means
$\bigcup_{c \ge 1} \mathsf{DTime}(2^{c^{n}})$ is closed under polynomial reduction. But what about $\bigcup_{c \ge 1} \mathsf{...
0
votes
0answers
8 views
Log-Space Reduction $USTCON\le_L CO-2Col$
I want to show that $USTCON\le_L CO-2Col$ (Log-Space reduction)
$USTCON$
The $s-t$ connectivity problem for undirected graphs is
called $USTCON$.
Input: An undirected graph $G=(V,E)$, $s,t \in V$. ...
2
votes
1answer
18 views
Number of equivalence classes in $P$
I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $...
2
votes
1answer
109 views
Showing that a language is NP Complete (advice)
I am currently getting ready for my final exam in computational models. I know that there aren't any rules or rule of thumb to show that a language is NP-complete and each problem has its own tricks, ...
1
vote
1answer
14 views
Complexity and hardness of undirected path
Let $PATH = \{(G,s,t) \mid \exists \text{path from}~s\text{ to }t\text{ in }G\}$, where $G$ is a directed graph. We know that $PATH$ is $NL$ complete. I am wondering what the complexity class of $PATH$...
0
votes
0answers
23 views
Why can't we generate the output of a cellular automata at time step t without first generating all the preceding states
Why can't we generate the output of cellular automata at time step t without first generating all the preceding states? Why can we do this for some functions? What features of a function does it ...
1
vote
0answers
14 views
How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?
For reference, the version of the nondeterministic time hierarchy theorem in question is this one:
The relevant portion of the proof in question (also from Arora-Barak) is here:
Arora-Barak define a ...
0
votes
0answers
19 views
$NTime(2^n) \subseteq NSpace(n^k)$ implies $EXP = PSPACE$?
Assume $NTime(2^n) \subseteq NSpace(n^k)$, for some fixed $k$. Is it possible to imply that $EXP = PSPACE$? and what about $NEXP = PSPACE$? It seems the answer might be YES, because this question ...
1
vote
1answer
19 views
Complexity of “half cycle”
I'm working on the following problem:
HALFCYCLE (HALFC):
Input:
A directed graph $G = (V,E)$.
Output:
Whether the longest cycle in $G$ has length $ \lfloor |V|/2 \rfloor$.
Prove that if $\...
0
votes
0answers
24 views
Space(n) and Space(n^2) implications
I've a problem where I have to prove the following statements:
(i) if $SPACE(n) \subseteq P \implies SPACE(n^2) \subseteq P$
(ii) if $P = SPACE(n) \implies SPACE(n) = SPACE(n^2)$
For the Space ...
2
votes
1answer
26 views
One-taped RAM vs Multi-taped RAM
In Turing Machine, we know that there's (fine-grained complexity) difference between one-tape, 2-taped and multi-taped TM, even though they could be simulated efficiently.
(Well, actually I'm not ...
0
votes
1answer
22 views
Prove Subset-Sum is NP-complete - Alternative reduction?
It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the ...
2
votes
1answer
34 views
How to calculate Big O of $T(n) = aT(n^b) + f(n)$?
I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log_b{a}}$ to $f(n)$ or
$O(n^{\log_b{a}} + f(n))$
Today I was faced with $T(n) = T(\sqrt n)...
0
votes
1answer
40 views
pseudo-polynomial reduction from 3-Partition to Partition
A problem $\Pi'$ is pseudo-polynomially reducible to the problem
$\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...
2
votes
0answers
37 views
Closure under polynomial reduction
Having some trouble generalizing when a complexity class $D$ is closed under polynomial reduction.
For instance, take the following examples:
$\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn^5})$
$\bigcup_{...
5
votes
1answer
65 views
Searching a Treasure
I was selected for a UG interview for computational natural science program and the following was one of the questions asked:
"Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the
...
0
votes
1answer
85 views
Proving NP completeness of maximal length path
I have this question to answer:
For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
2
votes
1answer
20 views
Showing Maximum Independent Set is $NP-hard$
I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$.
I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that ...
2
votes
1answer
23 views
NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}
Consider the following decision problems:
$CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with at least $k$ connected components}
$E-CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with exactly $k$ connected ...
2
votes
1answer
28 views
Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine
What is the difference between a Non-Deterministic Turing machine, Probabilistic Turing Machine and a Deterministic Turing Machine ?
0
votes
0answers
21 views
Splay tree amortized cost analysis
I am looking into the amortized analysis of splay trees and seem to be missing something.
Pretty much every resource uses the accounting method which I believe I grasp.
What confuses me is the part ...
3
votes
1answer
32 views
Quantum vs classic in NP-hard problems
Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?
2
votes
1answer
19 views
NL-Hardness of Target
When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve:
$ TARGET = \{<G, t> : t\ is\ reachable\ from\ ...
1
vote
0answers
8 views
About logarithmic cost model and bit complexity model?
So I heard that there are such models for finding time complexity of an algorithm as logarithmic cost model and bit complexity model. But from the information I have found in the internet, I cannot ...
3
votes
1answer
60 views
Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?
A minimum-spanning-tree (MST) path is always $V-1$ edges and a Hamiltonian Cycle (HC) is always $V$ edges.
Because the HC has an extra edge we could say that in general, the weight of every ...
1
vote
0answers
12 views
Log-space reduction from $USTCON$
Is it possible to use $USTCON$ log-space decision algorithm in order to show reduction from $USTCON$ to some other decision problem $A$? I mean - the reduction will run $USTCON$ decision algorithm and ...
1
vote
1answer
97 views
Can I simplify successive XOR operations?
I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions).
We have a rectangle of known ...
-1
votes
0answers
34 views
Are all uncomputable problems, undecidable?
Is there a proof that shows that:
"A problem is uncomputable iff it is undecidable"?
1
vote
1answer
19 views
Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?
We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...
1
vote
1answer
40 views
Decision problem - vertex with path to all other vertcies
Consider the following decision problem: Given a directed graph $G$, is there a vertex $v$ that has path to all other vertcies.
I am able to place this problem in NL, similarly to the strongly-...
0
votes
0answers
31 views
Clique of constant size
It is well known that Clique is a $NP$-Complete problem, But given some constant value $K$, finding whether a graph $G$ has a clique of size $K$, is always a log-space ($L$) class problem?
2
votes
2answers
34 views
How to verify Hamilton-Path in log-space?
Given an undirected graph $G$ and an undirected path $p$, Is it possible to verify $p$ is a Hamilton path in graph $G$ using logarithmic space? How is it possible to verify the path goes through all ...
3
votes
2answers
74 views
Why isn't the Generalized Super Mario Bros. obviously in NP?
It is shown in the paper: "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta that the Generalized Super Mario Bros. (SMB, for short) ...
0
votes
0answers
21 views
Solving a modular equation programmatically
Consider that I've a mathematical equation of the form:
$$ (6+4\times x)\text{ } mod\text{ } 22 = 0 $$
How can I solve this modular equation by using a program, efficiently? By trial and error, one ...
2
votes
1answer
26 views
Weak NP-completeness
I know that the Knapsack problem is weakly NP-complete. I also notice that on Wikipedia:
"A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it ...
1
vote
1answer
15 views
$stCON$ with path of length $≥ n/2$
The following problem seems very similar to the $stCON$ decision problem:
{$G, s,t | G = (V, E)$ such as $V$ is a graph, $s,t ∈ V$,
there exists in $G$ a simple path from $s$ to $t$ of length $≥ n/...
2
votes
1answer
25 views
Definition(s)/characterization(s) of intractability
I've been searching around for definitions of intractability, and I realized that despite being widely used, the concept of intractability (when talking about computing problems of course) is not ...
1
vote
1answer
28 views
Examples for Partial Combinatory Algebras
I am currently working on my Bachelor thesis about Turing Categories (see Introduction to Turing Categories [1]). In this context I got some questions regarding Partial Combinatory Algebras (PCAs), ...
1
vote
1answer
23 views
Reduction from NP-complete problem to unknown complexity problem and vice-versa
Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity.
Question:
If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required ...
1
vote
1answer
52 views
Space complexity of breadth-first search
I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$
nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor.
...
1
vote
2answers
41 views
$PSPACE$ not equal $DSPACE(2^n) $
It seems pretty obvious that $PSPACE$ is not equal to $DSPACE(2^n) $. Can this be shown using the space hierarchy theorem? Is that the most simple and straight-forward way?
-1
votes
0answers
26 views
Calculating Big-O and Big-Omega [duplicate]
I have understood big-O for a long time, and can easily determine the big-O of an algorithm or program. Just the highest order term, with factors removed (e.g. if run-time is $2n^2log(n)+3n+7$, then ...
3
votes
1answer
39 views
Pebble game lower bound?
This paper says pebble games have super linear lower bound for every fixed $k$ https://dl.acm.org/citation.cfm?doid=62.322433.
Why is it not considered proof of constructive example for a function in ...
5
votes
2answers
131 views
List of major Open Problems in Computational Complexity and their Likelihood?
I remember reading an article/paper (or perhaps a talk, most probably by Scott Arranson) where he lists the major open problems and their likelihood of being true or false in a table/graph. This is ...
1
vote
1answer
14 views
Log-space reduction - How to calculate overall space needed?
Assume A, B are two decision problems. Given a reduction from A to B that uses log^c1(n) space and an algorithm that solves B in log^c2(n) space, Can we determine some lower bound to the space needed ...
3
votes
1answer
46 views
Showing Cycle is NL-complete?
Consider the following decision problem :
Cycle:
Given a directed graph G, does G contains a directed cycle?
It is very clear why Cycle belongs to NL.
My question is - how to show Cycle is ...
4
votes
2answers
393 views
NL - iterating all edges of a graph in log space
Given a turing machine which has logrtmic space, and consists of an input tape and a working tape, Is it possible to iterate all egdes of an input graph? I know the answer is probably NO, because ...
2
votes
1answer
53 views
The Ising Model and Computational Complexity
I've been told recently that one can use the Ising model can find solutions to certain NP-hard problems, such as Clique, although it doesn't do so in polynomial time.
Googling gets a few Arxiv ...
2
votes
1answer
49 views
Number of Function Calls In Recursive Code
I am new to recursion. I am doing some practice questions and I was wondering what the technique is for going from some recursive code to identifying the number of function calls it makes.
...
2
votes
0answers
19 views
$NP$, $P^{TFNP}$ and $P^{UP}$
Is it possible
$NP\subseteq P^{TFNP}$ holds or
$NP\subseteq P^{UP}$ holds
without the polynomial hierarchy collapsing?
Is there problems in
one of each of the classes from $NP$, $P^{UP}$ and $...
