Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
porton's user avatar
  • 513
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 ...
porton's user avatar
  • 513
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 ...
Fernando's user avatar
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 ...
Omkar's user avatar
  • 1
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/...
rock_lee's user avatar
-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)...
Max's user avatar
  • 11
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? ...
Shreyas Shrawage's user avatar
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 ...
michaelprimo's user avatar
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 ...
Lex's user avatar
  • 21
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 ...
licheng's user avatar
  • 417
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$-...
user3445340's user avatar
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?
Simd's user avatar
  • 1,036
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 ...
Wisdom Iwueze's user avatar
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 ...
Lewis Trem's user avatar
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 ...
TokieSan's user avatar
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 ...
David Carpenter's user avatar
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, ...
Firavox's user avatar
  • 121
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" ...
Diode's user avatar
  • 1
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, ...
MWB's user avatar
  • 505
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 ...
Zee's user avatar
  • 243
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 ...
BreadthFirstTreeSearchFan's user avatar
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)$.
BreadthFirstTreeSearchFan's user avatar
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 ...
Neta R's user avatar
  • 13
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 ...
TheoryQuest1's user avatar
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 ...
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
  • 799
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 ...
L. breitman's user avatar
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 ...
sheesymcdeezy's user avatar
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 ...
Duda's user avatar
  • 111
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 ...
Dang Quang Vinh's user avatar
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 ...
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
  • 371
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 ...
Aland Ameer's user avatar
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 ...
mjg's user avatar
  • 1
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 ...
Daniel García's user avatar
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 $\...
rus9384's user avatar
  • 2,041
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 ...
Noone AtAll's user avatar
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, ...
414Sigge's user avatar
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 ...
Daniel García's user avatar
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 \...
Yuumita's user avatar
  • 153
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 ...
Karlo Vizec's user avatar
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 ...
TheoryQuest1's user avatar
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 ...
TheGuy's user avatar
  • 21
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}$ ...
RIM's user avatar
  • 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 ...
Xfae's user avatar
  • 13
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 ...
user167426's user avatar
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 ...
Aland Ameer's user avatar
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 ...
Rincewind's user avatar
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 ...
cartman's user avatar
  • 11
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 ...
UserA2000's user avatar

1
3 4
5
6 7
113