Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
-1 votes
0 answers
8 views

Prove/disprove that “NP = coNP if and only if A ≤P B and B ≤P A where A is an NP-complete languages and B is a coNP-complete language.”

I have a exam tomorrow and this is one of the sample question. I do not understand this. Is it possible for anyone to explain this to me in simplest way. Thanks in advance
Jamil9's user avatar
  • 1
3 votes
1 answer
181 views

Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

As the title states, I need to prove that the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard. I'm not looking for a solution but a clue or something to help me ...
OE.omergunr100's user avatar
0 votes
2 answers
67 views

Why is my O(n^2 * 2^n) code faster than O(n * 2^n) and O(2^n) codes for the LeetCode "Beautiful Subsets" problem?

I'm working on the LeetCode problem "The Number of Beautiful Subsets". I came up with a solution that runs in O(n^2 * 2^n). It's a very simple and ...
FluidMechanics Potential Flows's user avatar
2 votes
1 answer
42 views

Does NSPACE($n^2$) $=$ DSPACE($n^4$)?

From Savitch's Theorem, we know that NSPACE($n^2$) $\subseteq$ DSPACE($n^4$), but does the other direction hold? As far as I understand all we can say is that DSPACE($n^4$) $\subseteq$ NSPACE($n^4$).
BreadthFirstTreeSearchFan's user avatar
0 votes
0 answers
15 views

Derivation for BNF

Given a grammar for something like: h(x) or function(x) ...
User's user avatar
  • 9
3 votes
1 answer
35 views

Harder version of the k-partition problem

Given a sequence $q_1, \ldots, q_n$ of numbers, decide if the set $I=\{1,\ldots,n\}$ can be partitioned into $k$ sets $I_1, \ldots, I_k$ such that $\sum_{i\in I_1} q_i=\sum_{i\in I_2} q_i = \dots = \...
Lisa Ellingwood's user avatar
1 vote
0 answers
13 views

Is it known whether EXP is contained/not-contained in P/log?

Checking the complexity zoo (https://complexityzoo.net/Complexity_Zoo:P), I can only read that "if NP is contained in P/log then P = NP", so, right now, there must be no proof for EXP ...
441Juggler's user avatar
1 vote
1 answer
379 views

If coNP ⊆ NP, does that mean coNP = NP?

I had an exam, and one of the questions was Does ZPP = BPP if coNP ⊆ ZPP. I came down to coNP ⊆ NP and went on with "then coNP = NP", am i right?
Naneless's user avatar
0 votes
1 answer
17 views

Concise definitions for different types of computational problems

It is very common to define a decision problem $L$ in the following way. Let $f \colon \Sigma^{*} \to \{0,1\}$. Then $L = \{x \in \Sigma^* \mid f(x) = 1\}$. Effectively, $L$ contains all instances $x \...
user319109's user avatar
1 vote
0 answers
77 views

Constructing simple polygon from non-crossing orthogonal line segments

Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
Mohammad Al-Turkistany's user avatar
-1 votes
0 answers
23 views

Exercise: More on hashing for estimating sizes of sets

Let m and k be positive integers and let U = Um,k be a 2-wise independent family of hash functions from m bits to k bits. For any fixed set S ⊆ {0, 1} m and a randomly chosen h ∈ U, let I(S, h) be the ...
Rania Djeridi's user avatar
-1 votes
1 answer
31 views

Why do we use summations when computing time complexity?

When we consider the time complexity of an algorithm, we use summations to represent loops. For instance, the following loop through an array of $n$ length: ...
Jon Behnken's user avatar
0 votes
0 answers
18 views

$\mathsf{NP}$ vs. $\mathsf{coNP}$ and sparse sets

Consider the following statement: If there exists a sparse set of negative (the ones whose answer is no) instances $I$ such that for every negative instance $a$ ...
rus9384's user avatar
  • 1,654
0 votes
2 answers
40 views

Floating point operations in a zero padded Strassen multiplication

So I've seen other posts here that do discuss this, but I'm not quite sure how the time complexity (I think?) relates to the actual number of floating point operations done per second when you're ...
Applesauce44's user avatar
0 votes
0 answers
16 views

Boosting probability of Randomized approximation algorithms

Suppose $A$ is a randomized algorithm with following properties: The expected running time of $A$ is at most $\mathrm{poly}(n)$ When Opt$\geq c$, with probability at least $\mathrm{poly}(n)$ ...
Lagranngekmno4's user avatar
0 votes
1 answer
30 views

Robust maximum weight forests with weights on edges

In an undirected weighted graph with edge weights, the task is to find a spanning tree T. An adversary will delete two edges (not necessarily from T), and subsequently, we can add an edge (excluding ...
Toyllo's user avatar
  • 1
0 votes
0 answers
10 views

Critical Pair Determination in Knuth Bendix

In the Knuth Bendix completion algorithm, how does one identify all the critical pairs for an abstract term rewriting system? Does one have to iterate through each rule, and then identify which pairs ...
Navvye's user avatar
  • 1
3 votes
2 answers
85 views

How to Determining the Big O Complexity of a Recursive Function?

I'm struggling to determine the correct time complexity of a recursive function from an exam question. The function definition is as follows: fun (n) { ...
deaa aldeen's user avatar
1 vote
0 answers
28 views

NP-hardness of subset sum of multiple supersets

Given the following problem: Input: A set of disjoint sets $s_1, s_2, \dots s_n$, and an integer $K$ Question: Is there a set A with $|A|= n$ and $|s_i \cap A| = 1$ for all i from 1 to n, s.t. $\sum_{...
SimonNW's user avatar
  • 131
1 vote
1 answer
116 views

Why is the number of array accesses not considered in analyzing the complexity of mergesort?

I'm reading Robert Sedgewick's Algorithms and in the section about The complexity of sorting, I found the following paragraph: Proposition. Mergesort is an asymptotically optimal compare-based ...
Tran Khanh's user avatar
-6 votes
0 answers
41 views

What is the Time Complexity of following code?

What is the Time Complexity of following code? P_P(A[1..n]) { if (n==1) then return; for i=1 to n/2 A[i] = A[i] + A[i+n/2] P_P(A[1..n/2] }
Dattatraya Sakharam Adane's user avatar
1 vote
0 answers
49 views

Proof that $PREFIX_{TM}$ is not recognizable

We define $PREFIX_{TM}$ as the following language: $PREFIX_{TM} = \{ \text{ <M> | M is a TM, L(M)}\neq \varnothing \text{ and whenever M accepts w it accepts every prefix of w} \}$ We only ...
shaggy's user avatar
  • 23
1 vote
1 answer
45 views

Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer. The full description of the problem is: Is it possible to find a simple path (no ...
Lebecca's user avatar
  • 113
2 votes
0 answers
34 views

Satisfiability of a boolean formula with two occurrences of each variable with a special ordering

I am interested in the complexity of a special case of the boolean satisfiability problem: We are given a boolean formula, consisting only of the logical operators $\land$ and $\lor$ (that can be ...
SimonNW's user avatar
  • 131
1 vote
2 answers
116 views

Proof that HALF-3SAT is in P

We are told that assume that P $\neq$ NP , and that one of these languages is in P and the other one does not belong to P. I have managed to polynomially reduce 3SAT to FIRST-HALF-3SAT by duplicating ...
shaggy's user avatar
  • 23
0 votes
1 answer
36 views

Are NL-Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NL-C languages would produce a language not necessarily in NL-C....
Lior klunover's user avatar
-1 votes
1 answer
32 views

is my attempt correct? proof that L in P or in NPC? $L=\{G$ is an undirected graph on n vertices VC $U$ and an IS $I$ such that $|U|+|I|=n+10$ \}

I am facing a problem with the validity of the reduction function, may I get some assist in solving this issue, please? $L=\{<G>| G$ is an undirected graph on n vertices that has a Vertex Cover $...
maya cohen's user avatar
0 votes
0 answers
26 views

Largest Tetrahedra from a set of points

Problem Given a set of k points in 3D Euclidean space with k ≥ 4, find four points from the set that form a tetrahedra such that the volume of the tetrahedra is maximized. Attempted Solution Find ...
WakkaTrout's user avatar
1 vote
1 answer
13 views

Special case of 2-dim subset sum problem with only 0 and 1s

I am currently researching about a statistical project, where a special computer science problem showed up. I am wondering about the following: Suppose I have many two dimensional vectors all of the ...
Bailey Hor's user avatar
0 votes
0 answers
24 views

DTIME(t(n) logt(n)) relation to DTIME(t(n)) / sublin

I need some homework help and I'm not sure how to solve it. We have to show that DTIME($t(n) \text{ log } t(n)) \nsubseteq DTIME(t(n))/$sublin for every time-constructible $t(n)$. Sublin is the class ...
rock_lee's user avatar
1 vote
1 answer
43 views

Deciding if a regular language is empty can be done in polytime but deciding if it does not accept {0,1}* is not?

In my class we have discussed the fact that, given a representation $\langle R\rangle$ of a regular expression $R$, we can decide whether it accepts any string by first finding an equivalent NFA, and ...
Addem's user avatar
  • 367
0 votes
1 answer
20 views

NP-hardness of optimization with promise

Consider the Minimum Bisection problem, which asks, for a given $k$, whether the vertices of a graph can be partitioned into two parts of equal size such that the number of edges between these two ...
user166511's user avatar
0 votes
0 answers
11 views

Disjunctively Self-Reducible Languages and Their Relationship to NP

Can anybody help me in solving this question mentioned below.
pro's user avatar
  • 1
1 vote
1 answer
25 views

Size of circuit generating the solutions of a SAT problem

We have a satisfiable CNF formula $F$ which maps $\{0,1\}^n \to \{0,1\}$. Let us call $S\in \{0,1\}^n$ the set of inputs that satisfy $F$, i.e. $F(s)=1 \, \forall s\in S$. There is a circuit $C$ with $...
Doriano Brogioli's user avatar
0 votes
1 answer
35 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
3 votes
1 answer
99 views

Can remainder mod 2 be efficiently computed from addition 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
  • 131
0 votes
1 answer
38 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
43 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
4 votes
0 answers
40 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
  • 141
0 votes
0 answers
32 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
27 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
  • 493
0 votes
0 answers
21 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
  • 493
1 vote
1 answer
45 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
12 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
76 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
65 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
29 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
347 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
  • 405

1
2 3 4 5
110