Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
0 votes
1 answer
21 views

Complexity of algorithm waiting $e^{n}$ seconds

A dumb question in complexity theory. Let's consider an algorithm that solves the following problem: is $e^{n}$ time passed? ...
student's user avatar
0 votes
0 answers
21 views

Can remainder mod 2 be efficiently computed from addition, subtraction, and equality?

Suppose I have a programming language all of whose variables have natural number type. (So I cannot form higher-type objects, e.g., lists or trees, of natural numbers.) The only atomic commands I am ...
Siddharth's user avatar
  • 101
0 votes
0 answers
7 views

Show that $PLANAR \in co-NP \cap NP$

The fact that the language of planar graphs is in $co-NP$ is easy to show because the complexity of finding a Kuratowski subgraph is $O(|V|)$. But what about $NP$? Any help is appreciated.
Dave the Sid's user avatar
0 votes
1 answer
25 views

If $P=NP$, then $LCP \in P$

I want to prove that if we assume $P=NP$, then we can find the longest cycle (maximal number of vertices, no repeated edges, only repeated vertex is the starting one) in an undirected graph in ...
Dave the Sid's user avatar
0 votes
0 answers
8 views

Understanding Variable Quantification in Toda's Theorem Part 1

I am trying to understand the intricacies of Toda's Theorem, specifically focusing on the first part. In my exploration, I encountered a confusion regarding variable quantification that I hope someone ...
user4569455's user avatar
0 votes
0 answers
22 views

Variant of Generalized-Geography problem

Consider the "Generalized Geography" game: on directed graph G with selected start vertex, players take turns moving along edges, without ever going back to previously visited vertices. ...
Anuj's user avatar
  • 43
2 votes
0 answers
24 views

"Small" formulas for boolean functions

Theorem 10 in the following document: https://sites.math.rutgers.edu/~sk1233/courses/topics-S13/lec1.pdf states that every boolean function $f:\{0, 1\}^n\rightarrow \{0, 1\}$ has formula complexity $O(...
hello_123's user avatar
  • 121
0 votes
0 answers
27 views

Prove P/poly = BPP/poly

To prove the equivalence, we have to show that P/poly $\subseteq$ BPP/poly and BPP/poly $\subseteq$ P/poly thus P/poly = BPP/poly. Since BPP $\subseteq$ P/poly. My thinking is, we can also add poly to ...
rock_lee's user avatar
0 votes
1 answer
24 views

Are there known super-exponential problems?

Can you point a particular problem, all algorithms solving which are of a super-exponential time-complexity? I know that super-exponential problems exist, but is this a theorem of existence, or can a ...
porton's user avatar
  • 433
0 votes
0 answers
20 views

Is super-exponential complexity useful in practice?

Exponential time-complexity has a useful application in "practical" CS: NP-problems, NP-complete problems. Knowledge about this obviously helps in everyday programming. Can you give an ...
porton's user avatar
  • 433
1 vote
1 answer
34 views

Why is naive primality test not polynomial, while graph traversal is?

I am reading Sipser's Introduction to the Theory of Computation, and have trouble understanding the difference between polynomial and non-polynomial problems. When describing a PATH problem, where ...
Fernando's user avatar
-1 votes
0 answers
18 views

P with oracle to P is equal to P

How we can prove that P = P with P oracle Can we use this claim: if we have O in P then P with O oracle is in P and the proof for this claim is the following Allowing an oracle can only help compute ...
Rania Djeridi's user avatar
0 votes
0 answers
11 views

Relation between running time of Insertion sort and number of inversions

What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer. Consider Insertion sort ...
Omkar's user avatar
  • 1
1 vote
1 answer
62 views

Proof AM ⊆ NP/poly

Adleman's theorem proves that BPP ⊆ P/poly. It is implied here (https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol) that AM ⊆ NP/poly. BPP = BP $\cdot$ P ⊆ P/poly AM = BP $\cdot$ NP ⊆ NP/...
rock_lee's user avatar
-2 votes
1 answer
35 views

Is there a way to confirm a matrix multiplication solution in O(n)

Let A, B matrices of dimensions $\sqrt{n} * \sqrt{n}$ So that each has a total of n elements. Let there be a matrix C. Is there a known way to confirm wether C is the product of the two or not, in O(n)...
Max's user avatar
  • 1
1 vote
1 answer
59 views

NP, NP-Hard and NP-Complete

If a problem S is NP-Complete and we know that a problem Q is polynomial time reducible to S. Does that mean that Q belongs to NP? Also, when can we state that Q is NP-Hard but does not belong to NP? ...
Shreyas Shrawage's user avatar
0 votes
0 answers
32 views

How can I know the complexity of my conceptual game and solving it with an algorithm?

I made a really simple card game where you and your opponent have 6 cards and in a turn you can use only one of them and it will be discarded. The cards have a value and an effect. The cards, with ...
michaelprimo's user avatar
2 votes
1 answer
23 views

I am struggling to define the space complexity of a turing machine

I have a problem where I have a class A which is made up of problems which is solveable with a TM with space complexity O(logn). I now need to prove that the problem, where an input string of length n ...
Lex's user avatar
  • 21
3 votes
1 answer
341 views

Is determining the existence of a Hamiltonian cycle in a chordal graph NP-hard?

The Hamiltonian cycle problem asks if a given graph contains a Hamiltonian cycle. The Hamiltonian cycle problem belongs to the class of NP-complete problems. However, for some special classes of ...
licheng's user avatar
  • 365
2 votes
0 answers
27 views

Can a para-NP-Complete problem be $\Sigma^P_2$-Complete in its non-parameterized version?

I have a problem which (I think) have proven to be para-NP-Complete concerning some parameter $k$. However, I am certainly sure that the non-parameterized version of this problem is $\Sigma^P_2$-...
user3445340's user avatar
0 votes
1 answer
46 views

Is it possible there exists a $1.001^n$ time solution to a #P-hard problem?

We know that $\#P \subseteq P$ implies that $P = NP$. But is there any reason why a $1.001^n$ time algorithm shouldn't exist for a given $\#P$-hard problem?
Simd's user avatar
  • 996
1 vote
1 answer
22 views

Is the set of languages with verifiers running in polynomial time equal to the set of languages decidable by an NTM running in polynomial time?

I have seen two definitions for the set $NP$. One is that it is the set of languages decidable by a nondeterministic Turing machine (NTM) running in polynomial time, and the other is that it is the ...
Wisdom Iwueze's user avatar
1 vote
1 answer
25 views

Polynomial-Time Solvability Through NP-Completeness Reductions

Let A and B be NP-complete problems. Suppose I have established reductions from problem A to problem B and vice versa. Now, considering a specific instance (or set of instances) of problem A that can ...
Lewis Trem's user avatar
0 votes
0 answers
49 views

Why can't we say that P=NP if we have an infinite text file with solution for every possible SAT combination?

I believe that I have a misunderstanding in the P=NP problem while I was thinking of how can it be proved in a non-constructive manner. We know that we can build an infinitely large text file with ...
TokieSan's user avatar
0 votes
1 answer
17 views

Algorithms for stacking gage blocks

I'm looking for algorithms for stacking gage blocks. For those unaware, gage blocks are used in machine shops for measuring with high precision and come in sets something like this... Mitutoyo's 56 ...
David Carpenter's user avatar
0 votes
2 answers
68 views

Decision-Version of Linear Programming not in P?

Linear programming is the very common problem of computing $$\min_{Ax\leq b}c^\top x,$$ where $A\in\mathbb{R}^{n\times m}$, $b\in\mathbb{R}^n$, and $c\in\mathbb{R}^m$. This is an optimization problem, ...
Firavox's user avatar
  • 11
0 votes
1 answer
24 views

Can this Classic Regular Expression be simplified?

I have the following Regular Expression (classic Computer Science definition of Regular Expression, not PCRE or modern computer language RegEx): {(ΣΣ)*00(ΣΣ)*}Σ ∪ Σ{(ΣΣ)*00(ΣΣ)*} It "feels" ...
Diode's user avatar
  • 1
1 vote
0 answers
25 views

How could higher-order Datalog be more expressive than first-order Datalog?

According to this paper [1], higher-order Datalog is more expressive: ... we demonstrate that on ordered databases, for all k ≥ 2, ...
MWB's user avatar
  • 505
2 votes
1 answer
53 views

How to interpret Universal Quantifier in Alternating Turing Machines?

I am trying to read about Alternating Turing Machines (ATM) that have both existential and universal quantifiers for all their internal states. Given that these models are conceptual, I tend to ...
Zee's user avatar
  • 243
0 votes
0 answers
15 views

Why exactly does constructing a configuration graph of an $s(n)$ space bounded NDTM require that $s$ is space-constructible?

In "Computational Complexity: A Modern Approach", it states that to prove that $NSPACE(s(n))\subseteq DTIME(2^{O(s(n)})$, we can do the following: By enumerating over all possible ...
BreadthFirstTreeSearchFan's user avatar
0 votes
1 answer
36 views

In the proof that $DSPACE(S)\subseteq DTIME(2^{O(S)})$, why precisely do we require that $S=\Omega(\log n)$

I have read and understood various proofs, but have not been able to understand precisely why we require $S=\Omega(\log n)$.
BreadthFirstTreeSearchFan's user avatar
1 vote
1 answer
37 views

$L_1\in P$ , $L_2\in NP$, is it possible that $L_1\cup L_2 \in P$

Prove\Disprove\Prove that equivalent to $NP=P$ or $NP\ne P$ given $L_1 \in P$ , $L_2 \in NP$ is $L_1 \cup L_2 \in P$? Obviously $L_1 \cup L_2 \in NP$ because NP is closed under union and $P \subseteq ...
Neta R's user avatar
  • 13
0 votes
1 answer
19 views

What is the Computational Complexity of this Difference of Squares problem?

Consider a quadratic function over positive integers. For example say a simple function of the form: $f(n)=3n+4n^2$ Now given any positive integer $C$ find two integers such that: $f(i)-f(j) = C$ What ...
TheoryQuest1's user avatar
0 votes
1 answer
18 views

What is the set FirstHalves B? You can simply write out the set explicitly, enumerating the first four values

For any set of strings A, define the set FirstHalves A = {x∣∃y such that len(y) = len(x) and xy in A }. For example, FirstHalves {01, 111, 1010, 001101, 1011} = {0, 10, 001}, ie the first halves of ...
Firdaus Shallo's user avatar
-1 votes
1 answer
35 views

What is the computational complexity of the following problem

Given any number $N$ find a positive integer $k$ such that: $N + 12 k$ is a square. And the second case when we add an additional constraint that $k$ must be as small as possible.
J.Doe's user avatar
  • 789
4 votes
2 answers
140 views

What does $o_n(1)$ mean?

I'm trying to read the following article, and in the abstract they write: Let $\xi$ be a non-constant real-valued random variable with finite support, and let $M_n(\xi)$ denote a $n\times n$ random ...
L. breitman's user avatar
3 votes
1 answer
435 views

Proof for boosting success probability of a random algorithm with binary output

There is a theorem stating that, given a random algorithm with a binary output that has a success probability $\geq 2/3$, you can always create the another algorithm that solves the same problem but ...
sheesymcdeezy's user avatar
1 vote
0 answers
14 views

complexity theory: polynomial hierarchy for function problems / TSP with output

I'm searching for equivalent problem classes from the polynomial hierarchy to function problems. I have this problem similar to traveling salesperson, which imo lies in the second order of polynomial ...
Duda's user avatar
  • 111
0 votes
1 answer
28 views

Is every problem which can be solved by an algorithm using polynomial space in PSPACE?

I recently learned about the definition of PSPACE problems, which are a subset of decision problems that can be solved by using polynomial space. However, one thing I don't understand is when I asked ...
Dang Quang Vinh's user avatar
2 votes
1 answer
94 views

Determining whether two special variants of knapsack have the same optimal value

Given two unbounded knapsack instances, $K_1 = (W_1, weights, values), K_2 = (W_2, weights, values)$, where $W_1 \ne W_2$, what is the complexity of determining $v(K_1) = v(K_2)$ where $v$ returns the ...
rossignol's user avatar
10 votes
4 answers
3k views

Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?

Are there languages L1 ⊆ L2 ⊆ L3 where L1 and L3 are NP-Complete languages and L2 ∈ P? Would this imply P=NP? Thanks
Avi Tal's user avatar
  • 339
0 votes
2 answers
75 views

If we prove that NP = EXP, does that automatically prove that P != NP?

If P = DTIME(n^c) and EXP = DTIME(2^n), and we prove that NP = EXP, then it means that NP = DTIME(2^n). According to the time hierarchy theorem, the set of languages decided in O(f(n)) is bigger than ...
Aland Ameer's user avatar
0 votes
0 answers
12 views

Are there non-brute-force algorithms for longest or shortest beta reduction path?

Consider the related problems of, given a strongly normalizing lambda term, computing the longest and shortest paths ending in a normal form. In terms of bits of input the optimal complexity is some ...
mjg's user avatar
  • 1
2 votes
2 answers
96 views

No Neighbor Vertex Cover

Let $G=(V,E)$ be an undirected connected graph with a set of vertices $|V|$ and a set of edges $|E|$. A set cover $D$ satisfies $D \subseteq V$ and $uv \in E \implies u \in D \lor v \in D$. A variant ...
Daniel García's user avatar
3 votes
1 answer
31 views

Is boolean formula equivalence problem for 2-CNFs $\mathsf{coNP}$-hard?

The problem: Given two boolean formulas in 2-CNF, decide if they are equivalent. I know that the problem is $\mathsf{coNP}$-hard when at least one formula is in 3-CNF. However, the same proof of $\...
rus9384's user avatar
  • 1,632
1 vote
1 answer
47 views

Is "Length of Longest Increasing Subsequence" in L?

I can't find space complexity of this problem with search engines. I think I have NL algorithm for it (just a basic "one by one non-deterministically accept values if possible"), but I ...
Noone AtAll's user avatar
4 votes
2 answers
89 views

Fizz Buzz and pseudo-polynomial time

I am currently taking a course on algorithms, and when reading about the 0/1 Knapsack Problem on Wikipedia I came across a technique which uses dynamic programming and supposedly runs in $O(nW)$ time, ...
414Sigge's user avatar
1 vote
1 answer
77 views

Constrained Maximum Flow Minimum Cost

Let $G=(V, E)$ be a directed network with a set $V$ of vertices and a set $E$ of edges. Two vertices are distinguished, $s,t$ which are the source and sink respectively. Each edge $(i, j)$ has an ...
Daniel García's user avatar
4 votes
1 answer
156 views

Size of the certificate as a property of the problem

Suppose I have a decision problem $\mathcal{L}\subseteq\Sigma^*$ and a verifier $V$ that recognizes $\mathcal{L}$, i.e. $L(V)=\mathcal{L}$. Let's arbitrarily choose some certificate $c(w)$ for $w \in \...
Yuumita's user avatar
  • 153
0 votes
1 answer
24 views

Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?

I know that exponential time complexity is $ O(k^n) $, where $k$ is some constant and $n$ is the input size, and that subexponential time is anything slower than that, $o(k^n)$ . If we define ...
Karlo Vizec's user avatar

1
2 3 4 5
109