All Questions
Tagged with complexity or complexity-theory
5,612 questions
0
votes
1
answer
39
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 ...
0
votes
0
answers
25
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 ...
1
vote
1
answer
49
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
...
0
votes
0
answers
25
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
...
1
vote
1
answer
115
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/...
-1
votes
1
answer
38
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)...
1
vote
1
answer
67
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?
...
0
votes
0
answers
34
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 ...
2
votes
1
answer
47
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 ...
3
votes
1
answer
362
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 ...
2
votes
0
answers
32
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$-...
0
votes
1
answer
50
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?
1
vote
1
answer
30
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 ...
2
votes
1
answer
44
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 ...
0
votes
0
answers
58
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 ...
1
vote
1
answer
30
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 ...
0
votes
2
answers
91
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, ...
0
votes
1
answer
28
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" ...
1
vote
0
answers
39
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,
...
2
votes
1
answer
62
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 ...
0
votes
0
answers
18
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 ...
0
votes
1
answer
40
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)$.
1
vote
1
answer
48
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 ...
1
vote
2
answers
50
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 ...
0
votes
1
answer
20
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 ...
-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.
4
votes
2
answers
158
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 ...
3
votes
1
answer
574
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 ...
1
vote
0
answers
19
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 ...
0
votes
1
answer
29
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 ...
2
votes
1
answer
97
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 ...
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
0
votes
2
answers
99
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 ...
0
votes
0
answers
15
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 ...
2
votes
2
answers
118
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 ...
3
votes
1
answer
44
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 $\...
2
votes
1
answer
59
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 ...
4
votes
2
answers
98
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, ...
1
vote
1
answer
106
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 ...
4
votes
1
answer
160
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 \...
0
votes
1
answer
30
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 ...
0
votes
0
answers
33
views
Is this version of SAT NP-Complete?
Given a SAT instance such that:
Each clause is of length at most 4.
Negative literal occurs only in clauses of length=2.
Each length 2 clause has at most 1 negative literal.
Is this version of SAT ...
2
votes
0
answers
58
views
Approximate the parity function in L1-norm
Consider the parity function $MOD_2(x) = x_1 \oplus \cdots \oplus x_n$ for $x \in \mathbb{F}_2^n$. I am concerned about the degree bounds for a real polynomial $f$ which approximates $MOD_2$ well in ...
0
votes
0
answers
38
views
reduction from $\#permanent _{-1,0,1}$ to $\#permanent _{0,1,2,3,\dots,n}$
i want to prove the reduction from $\#permanent _{-1,0,1}$ to $\#permanent _{0,1,2,3,\dots,n}$ and from $\#permanent _{0,1,2,3,\dots,n}$ to $\#permanent _{0,1}$ ( to prove that $\#permanent _{0,1}$ ...
1
vote
1
answer
87
views
Is this intersection set problem NP-Hard?
Suppose we have collection of n sets $S_1, S_2, \dots, S_n$. Each set has a size of at least $k$. We know for sure that $\exists k$ sets where all of them contain the same $k$ elements; $|S_1 \cap S_2 ...
0
votes
1
answer
19
views
Two transition functions def of NP
I've seen a definition of NP alluded to in different texts where at each step an NDTM makes a nondeterministic choice between two transition functions and behaves accordingly. It seems like even in a ...
1
vote
0
answers
41
views
How could it be the case that NP != EXP? Do we know of any problems in EXP that are not in NP? [duplicate]
I know that NP is a subset of EXP, but I cannot find any resources talking about whether NP = EXP or not.
My intuition tells me that any problem that requires exponential time to be solved with a DTM ...
0
votes
0
answers
25
views
Reductions trick where you halt and reject after polynomial time
There's a standard trick I've heard about in reductions where you just halt a machine and reject after some polynomial amount of time if it hasn't accepted yet. Can this be applied to nondeterministic ...
1
vote
0
answers
35
views
Hardwiring advice (bit string) into Turing machine
In paper, page 5, 1st paragraph, it is stated that:
Notice that an n-state Busy Beaver, if we had it, would serve as an O(n log n)-bit advice string, “unlocking” the answers to the halting problem ...
4
votes
0
answers
76
views
Extending Fagin's Theorem to the Polynomial Hierarchy
Fagin's Theorem (see Wikipedia and these lecture notes) states that there is an equivalence between second-order logic (SOL) formulas with existential quantifiers, and problems in NP.
I was wondering ...