Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
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. ...
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 ...
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 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 ...
-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!
-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)
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 ...
-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)?
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 ...
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. ...
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 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 ...
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 ...

1
2 3 4 5
102