Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,084
questions
0
votes
0
answers
9
views
What is the complexity of computing logspace bounded Kolmogorov complexity?
We know that the time bounded and space bounded variants of Kolmogorov complexity are respectively NP-complete and PSPACE-complete. However, is there anything known about the complexity of the ...
1
vote
1
answer
15
views
What Complexity Class Contains $QSAT_{\log n}$?
It is known that $QSAT$ is $PSPACE$ complete, and it is known that $QSAT_i$ is $\Sigma_i$ complete for any constant $i$. However, what if we had $QSAT_{\log n}$? That is, $QSAT$ where the quantifiers ...
- 113
0
votes
0
answers
21
views
The computational complexity of a variant of algorithm for the TSP (Travelling Salesman Problem)
What is the algorithm's computational complexity for a variant of the Travelling Salesman Problem, where every node must be visited at least once, meaning that a node can be visited more than once? (...
1
vote
1
answer
29
views
Understanding the Strong Exponential Time Hypothesis
Let $n$ be the number of variables in the input formula and $m$ the number of clauses. Define $s_k = \inf\{\delta : k\text{-SAT can be solved in } 2^{\delta n} \text{ time}\}$. The strong exponential ...
- 15
0
votes
1
answer
36
views
Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?
Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when ...
0
votes
1
answer
39
views
Time complexity of $\mathsf{NP}$ problem under assumption of $\mathsf{P} \neq \mathsf{NP}$
A simple question, but I can't find an answer in quite the form I'm looking for:
Assume $\mathsf{P} \neq \mathsf{NP}$, and thus $\mathsf{P} \subsetneq \mathsf{NP}$. If we have $L \in \mathsf{NP}$ and $...
- 3
2
votes
0
answers
28
views
Problems with proof of NP-completness of SAT following Cooks original paper
I am currently in the process of trying to understand the original proof of NP-completeness of SAT given in the seminal paper by Cook [COOK71] and have struggled with a few of the details of the proof ...
0
votes
4
answers
54
views
What is the lower bound of n factorial
The upper bound of $n!$ is $O(n^n)$. But I am not getting a way to compute the lower bound of n!.
We can write $n! = n\times(n-1)\times(n-2)\times\dots\times 1$. I can easily put all the terms as 1. ...
- 21
3
votes
2
answers
516
views
Is this variant of Exact Path Length Problem easy or NP Complete
I was reading about the longest path problem and it is NP Complete.
What about the problem where we need to find a path of some exact length $K$. All edges are directed. We are also allowed to repeat ...
- 45
0
votes
1
answer
61
views
Are there any implementations of algorithms on hardware that are (nearly) optimal?
Consider the notion of optimal implementation as follows. Suppose we have some algorithm $A$ whose execution for some problem of size $N$ requires $T(N)$ operations (e.g. arithmetic operations). A ...
- 103
0
votes
0
answers
20
views
Are all languages determined in exponential time NP languages?
According to the theorem, if $L \in NP$, then $L$ can be determined by a deterministic Turing machine in exponential time.
So, are all languages determined in exponential time NP languages?
- 163
0
votes
0
answers
15
views
Is this language PSPACE complete
Prove $PSPACE$-completeness of the language $READALLEXACT$ = $\{$$(M, x, 1^ s , t)$ | $A$ deterministic Turing machine $M$ on input $x$ reads all bits of the input in exactly $t$ steps and using no ...
- 1
0
votes
1
answer
35
views
Prove that $coNP \neq NTIME(n^2)$
I need to prove that
$coNP \neq NTIME(n^2)$ using time hierarchy theorem.
as we know $DTIME(n^4)\subseteq P\subseteq coNP$
from time hierarchy theorem we can derive that $DTIME(n^4) \not \subseteq ...
- 1
1
vote
1
answer
49
views
What data structure/s can I use for fastest lookup of a permutation between two arrays of pairs (preserving order)?
I'm trying to figure out a more efficient solution to the following problem.
Dataset: A set of arrays of key-value pairs (K, V). The arrays have varying lengths, ...
- 111
-1
votes
1
answer
33
views
A sufficient condition for unsatisfiability
Let $\varphi = \bigwedge C_k$, in which $C_k$ is a clause in X3SAT (exactly-one 3SAT or one-in-three 3SAT). That is, $C_k = (l_i \odot l_j \odot l_u)$ such that $l_i \in \{x_i, \overline{x}_i\}$ for ...
0
votes
2
answers
101
views
Can you help me in finding an algorithm that finds the first unique number in an array with lowest position?
I have the following problem to solve:
Given a non-empty array A consisting of N integers, the task is to find the first unique number in the array. A unique number is defined as a number that occurs ...
1
vote
1
answer
25
views
Proof that STCON is in NL
What is the proof that STCON
(returns 1 if there is a path in the directed graph $G = (V,E)$ from $ s \in V$ to $t \in V$ and else, 0.
is indeed in NL? (Non-deterministic turing machines with ...
-4
votes
0
answers
25
views
Prove that the language $ALMOSTSC$ is $NL$-complete
Prove that the language $ALMOSTSC$ $=$ $\{$$G$ | $G$ is an oriented graph which becomes strongly connected after adding one edge$\}$ $(a)$ lies in $NL$ and $(b)$ is $NL$-complete.
I'm making a problem-...
- 1
-4
votes
0
answers
35
views
Prove that $P ^A = NP^A$ with probability $1$
Consider a random oracle $A$ constructed as follows: there are no words of odd length, and for each length independently of the others there is exactly one word which is a square (i.e. a concatenation ...
- 1
-5
votes
0
answers
34
views
Prove that the function grows faster than any computable function
Prove that the function $BB_{10}(n)$ that returns the maximal number of blocks $10$ in a row in the Turing machine with $n$ states on empty input, grows faster than any computable function.
https://en....
-3
votes
0
answers
19
views
Classify the language $UNIVERSALCLIQUE$ in polynomial hierarchy
Classify the language $UNIVERSALCLIQUE$ = $\{$$(G, V_1, V_2, k, l)$ | $G = (V, E)$ is undirected graph, $V = V_1\sqcup V_2$, and some clique of $k$ vertices in graph $G_1$ together with any clique of $...
- 1
-4
votes
0
answers
18
views
Prove that the language TWOCYCLESPERMUT lies in $L$
Prove that the language $TWOCYCLESPERMUT$ = $\{$$σ$ | in the partition of permutation $σ$ into cycles there are exactly $2$ cycles$\}$ lies in $L$. (The permutation is represented as a list of $n$ ...
- 1
-4
votes
0
answers
23
views
Prove PSPACE-completeness of the language READALLEXACT
Prove $PSPACE$-completeness of the language $READALLEXACT$ = $\{$$(M, x, 1^ s , t)$ | $A$ deterministic Turing machine $M$ on input $x$ reads all bits of the input in exactly $t$ steps and using no ...
- 1
-3
votes
0
answers
24
views
Classify in polynomial hierarchy the language $SUBSUBSETRANGESUM$
Classify as precisely as possible in polynomial hierarchy the language $SUBSUBSETRANGESUM$ = $\{$$(X, L, R, k)$ | the size of the smallest subset $Y$ of the set of natural numbers $X$ such that for ...
- 1
-1
votes
1
answer
38
views
Prove the NP-hardness of problem
Prove the $NP$-hardness of $CONNECTEDNESS$ - the problem of counting over an oriented graph $G$ and two vertices
$s$ and $t$ the number of subgraphs of $G$ in which from $s$ to $t$ can be traversed by ...
- 1
-3
votes
0
answers
23
views
Problem of checking two arithmetic schemes for equality
Let the problem of checking two arithmetic schemes for equality not lie in $ZPP$. Prove that then the set of
of triples of which exactly two schemes coincide lies in $BPP$, but not in $RP$.
I'm doing ...
- 1
-4
votes
0
answers
24
views
Come up with a probabilistic algorithm and derandomize it
Come up with a probabilistic algorithm to approximate the solution of the $MAX4COL-SMALLDIFF$ problem with an accuracy of $\frac{3}{8}$
and derandomize it by the conditional expectation method.
(The $...
- 1
-1
votes
0
answers
18
views
Prove that language DuplBit is in coRP
Let $A ⊂ {0, 1}^∗$ and $A ∈ coRP$. Prove that the language $DuplBit(A)$ consisting of all the results of doubling one
bits in some word from $A$, also lies in $coRP$.
- 1
-2
votes
0
answers
34
views
Prove that language is in $NC$
Prove that the language CYCLE = $\{$$A$ | oriented graph with adjacency matrix $A$ contains oriented
loop$\}$ lies in $NC$. Specify as precisely as possible the class $NC^k$
or $AC^k$
to which it ...
-1
votes
0
answers
20
views
Prove that language is in $DTIME(n^2)/_{n^2}$
Let $∀n |A ∩ \{0, 1\}^n| ≤ n$. Prove that $A ∈ DTIME(n^2)/_{n^2}$.
Def. The class $DTIME(f(n))/_{a(n)}$ is the set of languages $L$ for which there exists a Turing machine $M$ and a sequence of words ...
0
votes
1
answer
19
views
Transforming a Travelling Salesman Problem to a Maximum Clique Problem
Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly ...
- 1
0
votes
0
answers
18
views
Order of time complexity in computing $R\sin(2\alpha)$ VS $2R\sin(\alpha)\cos(\alpha)$
I was wondering, in terms of complexity and "precision", what are the differences, if any, netween the computation of
$$2R \sin(\alpha)\cos(\alpha) \qquad \qquad \text{and} \qquad \qquad R\...
- 101
0
votes
1
answer
38
views
Is graph isomorphism $P$-hard?
Intuitively speaking, it would seem like the graph isomorphism problem (which might be $NP$-intermediate) should be $P$-hard. But maybe it's not? Or maybe it's an open question?
If it is indeed $P$-...
- 717
0
votes
1
answer
40
views
Which definition of decidable is correct?
Please note I don't use any of the "verifier" notation, I only concern definitions made with DTM and NTM .
Now there are two definitions of decidability:
1. A set (predicate) is decidable (...
- 3
-1
votes
0
answers
26
views
Which of the following statement about complexity analysis are correct?
My answer is ABCDE. I'm pretty sure BCE are correct, but AD are not sure. It would be grateful if someone can give a concise explanation of AD for me!
- 11
-3
votes
1
answer
35
views
Prove or disprove: f(n-1) is omega(f(n))
Prove or disprove: f(n-1) is omega(f(n)).
I actually need a more specific example of this but I thought this claim was interesting.
I want to know if (n-1)log(n-1) is omega(nlogn)
- 3
0
votes
1
answer
55
views
Is there a standard name for the complexity class "embarassingly parallel"
So i'm defining the embarassingly parallel complexity class as the set of decision problems which can be solved in time $O(T(n))$ on a single computer and in time $O(T(n)/g(n))+O(\log(g(n))$ if you ...
- 353
-1
votes
2
answers
67
views
Is P vs NP, a paradox in a hypothetical perspective?
In a hypothetical scenario, where a precise and formal definition does not exist here, and thus expressed with analogies and verbal reasoning for the sake of simplifying the P, NP problem.
A(lan) ...
-2
votes
1
answer
28
views
NSPACE(n^2) and DSPACE(n^2) class problems
What problems belong in NSPACE(n^2) and DSPACE(n^2) class? Examples?
- 3
3
votes
2
answers
78
views
Complexity of taking recursive modulo
Given 2 integer $M$ and $N$, a recursive modulo is $M \bmod (M \bmod (M \bmod ...(M \bmod N)$ until the result is 0. What is its time complexity?
I guess that it's $O(log(M))$ but I can't prove it.
-1
votes
2
answers
55
views
Does superpolynomial lower bounds of a problem in $NP$ mean that $P \neq NP$?
If one proves that the lower bounds of an $NP$ problem, are not bounded by any polynomial, is this enough to prove that $P$ does not equal $NP$?
- 1
1
vote
1
answer
35
views
Independent set problem for graphs with very large independent sets
Is there a number $\alpha < 1$ such that the independent set problem is polynomial for input graphs whose independence number is at least $\alpha n$ (where $n$ is the number of vertices)?
- 113
0
votes
2
answers
148
views
Finding the time complexity of a prime factorization algorithm
In this question, I'm going to introduce a prime factorization algorithm which I'm working on as my personal project.
I may attach a Python code to introduce the algorithm. If it contravenes the rule ...
- 11
2
votes
2
answers
42
views
Describing the set of Running Time of all Turing Machines
Consider the set of all valid Turing Machines descriptions $T_{All}$, and the set of functions that denote the real (not asymptotic) running time of Turing Machines in $T_{All}$, lets call it $R_{All}$...
- 23
1
vote
1
answer
35
views
Kolmogorov complexity and data compression revisited
The question of the relationship between Kolmogorov complexity and data compression is rather difficult.
However, at the heuristic level, the complexity of an object and the rate of its compression by ...
- 111
1
vote
1
answer
18
views
Difference b/w Functional and Decisional Problem's computational complexity
I am trying to understand the difference b/w functional and decisional problems. The core as I understand is this:
Functional Problems: Given an input $x$ we calculate some function $f(x)=y$ over it.
...
- 45
0
votes
0
answers
12
views
Natural Problems not in P [duplicate]
From Time-Hierarchy theorem we know that there are problems that are not solvable in polynomial time. But I would like to know some natural problems that are provably not in P. Does anyone know a ...
0
votes
1
answer
14
views
Equivalence of echo state networks and DFAs/NFAs
Echo state networks are theoretically equivalent to DFAs/NFAs, but how would you use an ESN to parse a regular language? Would you just feed many different input strings, some from the language and ...
- 1
1
vote
1
answer
48
views
The meaning of Tautology and Contradiction in Complexity theory
I recently had this question answered on stack exchange:
if X is in NP but Y is not in NP then can X be reduced to Y?
The answer proposed a counter example using an element of complexity theory I had ...
- 29
0
votes
1
answer
58
views
Is there a known method for reducing the problem of prime factorization to the problem of determining if a hamiltonian path exists?
I hope this question is not out of place here, but I am currently attempting to implement the problem(a reduction algorithm) stated in the Title. I included the steps I am following as of now and an ...
- 73