Skip to main content

Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
0 votes
0 answers
4 views

If A ∈ coNP, B ∈ NP and $NP \neq coNP$, is it possible to Karp reduce A to B?

If A $\geq_p$B and $B\in NP$, $A\in coNP$, then we can build a Turing machine $M_A$ using $M_B$ machine of B. Input: w We make a new word with a reduction function $f(w)$. Then we run $M_B$ on $f(w)$ ...
Naneless's user avatar
1 vote
0 answers
18 views

Exactly 4 witnesses

For a language $L$ to be in $NP$ it suffices for a witness $y$ to exist and a (polynomial) verification algorithm $A$, s.t. $x\in L$ iff there exists a (polynomial size) $y\,$ s.t. invoking $A$ on $x,...
Benicio Agüero's user avatar
7 votes
1 answer
90 views

Determining whether there's a permutation that satisfies a linear equation

Given a positive integer $n$ and integer coefficients $c_1, c_2, c_3, c_4,..., c_n$, the goal would be to find a $\sigma \in S_n$ ($S_n$ is the group of permutations on $\{1,2,...,N\}$) such that: $$\...
Bryle Morga's user avatar
2 votes
1 answer
18 views

Limited constant degree HamCycle

Let $G=(V,E)$ be a directed graph. I am interested in a "relaxed" version of the HamCycle problem. In my first case, the degree of each vertex is exactly 6, such that: 3 are outgoing edges ...
Eric_'s user avatar
  • 465
6 votes
2 answers
936 views

What is the difference between NP=EXP and ETH, and what does the community believe about their truth?

We know that $NP\subseteq EXP$ but not whether it is strict. The Exponential Time Hypothesis (ETH) states that SAT cannot be solved in subexponential time. My understanding is that most computer ...
user56834's user avatar
  • 3,982
1 vote
0 answers
27 views

Chromatic Polynomial of Hamming Graphs

I'm trying to calculate the chromatic polynomial of different Hamming Graphs , especially $H(3, 3) = K_3 \times K_3 \times K_3$, so the Graph Cartesian product of the complete graph with three ...
Dan's user avatar
  • 61
1 vote
1 answer
57 views

Algorithm to sort array into K increasing subsets?

Let's say we got an array of size n with real numbers, and a natural number k. n must be multiple of k. We want to sort the array in a way that, when we divide this array into k subsets of equal size, ...
user166586's user avatar
2 votes
0 answers
30 views

Complexity class BPP, but with only expected polynomial running time

The complexity class BPP requires that the running time be guaranteed polynomial, though with only a 2/3 chance of the correct output. ZPP, on the other hand, guarantees correct output, but now only ...
Mike Battaglia's user avatar
2 votes
0 answers
30 views

Complexity of strong graph realization problem

Given a simple graph $G$, let $k^{th}$ degree of a vertex $v_i\in G$ denote the number of vertices that have distance $k$ from $v$. Notice that first degree is equivalent to degree by standard ...
rus9384's user avatar
  • 1,684
2 votes
1 answer
99 views

NP-hardness of solving systems of *homogeneous* polynomial equations

It is well-known that deciding if a system of quadratic polynomial equations in several variables admits a solution in a finite field is NP-complete. There is a simple reduction from 3SAT, that works ...
Charles Bouillaguet's user avatar
3 votes
1 answer
290 views

Prove that "max independent set is larger than max clique" is NP-Hard

We define B as: $B = \{ <G> | \text{ G is an undirected graph in which} \\ \text{the number of vertices in the largest independent set} \\ \text{is greater than the number of vertices in the ...
shaggy's user avatar
  • 63
3 votes
1 answer
55 views

Cover a set of points using subintervals of a list of intervals

Given a set of points $\{p_1, p_2, \dots p_n\}$ and a set of intervals $I =\{[a_1, b_1], \dots [a_m, b_m]\}$, you are asked to find a set of subintervals $S = \{[c_1, d_1], \dots [c_m, d_m]\}$ where $[...
SimonNW's user avatar
  • 161
2 votes
1 answer
48 views

Is there a formal methodology for determining time complexity of an implementation of an algorithm?

Basically what the title says. take for example a simple function: def swap(a,b) temp = a a = b b = temp This one is pretty easy to solve intuitively. if we ...
UNRESTR1CTED's user avatar
3 votes
1 answer
363 views

Easy/hard NP-hard problems on perfect graphs

Three problems --- Graph coloring, Stable set, and Clique --- are known NP-hard problems (on general graphs) that can be solved in polynomial time, when we know that the given graph is a perfect graph....
Lisa E.'s user avatar
  • 516
4 votes
0 answers
55 views

Deterministic solution of "nuts and bolts" problem

How are the samples in "Matching nuts and bolts" paper in chapter two chosen deterministically to achieve $O(n^{1.5})$ complexity? I don't see how projective planes can help here.
Gh0st's user avatar
  • 41
1 vote
1 answer
61 views

What did Gill write in 1972 about P and NP?

Cited in Kozen's paper on subrecursive indexing (here) appears a paper by John Gill called "Axiomatic Independence of the question P=NP?". What is this paper about and how does it relate to ...
user6767509's user avatar
-1 votes
1 answer
47 views

Does P=BPP implies we can construct a Boolean circuit for a fair coin flip?

I would precisely like to know if the conjecture BPP=P implies the following: Is it possible to build a classical Boolean circuit whose outputs are statistically indistinguishable from a fair coin ...
108_mk's user avatar
  • 101
0 votes
1 answer
87 views

Negating a Quantified Boolean Formula (QBF)

I'm reading about quantified boolean formulas. One sentence mentions: You should also verify that the negation of the formula $Q_1x_1\cdot\cdot\cdot Q_nx_n \phi(x_1, ..., x_n)$ is the same as $Q^{\...
itstwelvehere's user avatar
2 votes
0 answers
22 views

Tree width given path decomposition

I have a family of graphs whose path decompositions I know. Is it possible to compute the tree-width of these graphs in polynomial time?
Lisa E.'s user avatar
  • 516
3 votes
4 answers
432 views

Undecidable problems in finite graphs

Are there any natural questions in finite graphs (or digraphs) that are undecidable?
Lisa E.'s user avatar
  • 516
1 vote
1 answer
25 views

Emphasizing the Coefficients of the Leading Order and Using Big O Notation for the Remainder

I am trying to understand the correct application of Big O notation to polynomial expressions, including terms with negative coefficients. For example, consider the polynomial $2n^3-2n^2+n+1$, where $...
Byeongyong Park's user avatar
1 vote
0 answers
48 views

Is it correct to say that DepthFirst Search has the space complexity O(bm) and DepthFirst IterativeDeepening O(d)?

Is it correct to state that the space complexity of Depth-First Search (DFS) is $O(bm)$ and that of Iterative Deepening Depth-First Search (IDDFS) is $O(d)$? Here, $b$ represents the branching factor, ...
Martin's user avatar
  • 11
0 votes
1 answer
43 views

Help me prove me the following claim: $NP = coNP$ Iff $coNP \cup NP$ is closed under intersection

I was able to prove the first direction which is the assumption that $NP=coNP$, but I am unable to prove the second direction: Assuming that the union group is closed, how can it be proved that $NP=...
Nir Binjamin's user avatar
3 votes
1 answer
44 views

Usage of matrix multiplication for distance products

This is more of a validation question, for the current best known results. On one hand, we have classical matrix multiplication. Its running time is denoted as $n^\omega$. On the other, we have ...
Mařík Savenko's user avatar
1 vote
0 answers
35 views

Graph with an exponential number of paths

I am looking at the language $F$ containing all $G,v_0,v_1$ s.t.: $G$ is undirected $G=(V,E)$ $v_0,v_1\in V$ $|V|=n$ There are $2^n$ paths between $v_0$ and $v_1$ I would like to prove that $F\notin ...
Benicio Agüero's user avatar
1 vote
1 answer
100 views

Polynomial solutions, one less

Let $L$ be a language in the class $FP$ of all polynomial-time solvable problems. The class $FP$ is defined by having a TM $M$ s.t. for any $x$ it computes in polynomial time a $y$ s.t. $(x,y)\in L$. ...
Dan D-man's user avatar
  • 524
5 votes
0 answers
98 views

Minimum cost path connecting exactly K vertices

I came across a situation in real life that maps to this optimization problem: Given a fully connected, undirected, weighted graph with $N \ge K$ vertices, find the simple path connecting exactly $K$ ...
InfiniteSnow's user avatar
0 votes
0 answers
35 views

Equivalent definition of a PTNDTM?

$NP$ is the class of problems with a polynomial time non-deterministic turing machine which can determine whether an input is in a certain language or not. It can be seen as polynomial time ...
Benicio Agüero's user avatar
-2 votes
0 answers
12 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
4 votes
1 answer
215 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
77 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
56 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
19 views

Derivation for BNF

Given a grammar for something like: h(x) or function(x) ...
User's user avatar
  • 11
3 votes
1 answer
42 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 E.'s user avatar
  • 516
5 votes
1 answer
64 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
390 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
0 votes
0 answers
124 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
24 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
35 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
1 vote
0 answers
20 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,684
0 votes
2 answers
41 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
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
4 votes
2 answers
97 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
30 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
  • 161
1 vote
1 answer
117 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
1 vote
0 answers
55 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
  • 63
1 vote
1 answer
46 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
37 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
  • 161

1
2 3 4 5
110