Skip to main content

Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
2 votes
0 answers
24 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 ...
1 vote
2 answers
62 views

Subquadratic multiplication of polynomials in the max-plus/tropical semiring

Is there an algorithm to multiply two polynomials with coefficients in the max-plus semiring $(\mathbb{Z}\cup\{-\infty\}, \max, +)$ which is faster than the trivial one? I'm interested in the ...
1 vote
1 answer
45 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, ...
2 votes
1 answer
95 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 ...
0 votes
2 answers
4k views

Given n numbers How to find out a set of numbers whose sum equal to a certain given number

I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s. ...
1 vote
2 answers
653 views

IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?

The SUBSET SUM decision problem consists of poitive integers a1,...,an; b. We wish to know if for some subset S of the indices, $\sum_{i \in S}a_i = b$ I want to prove that if b is given in unary(...
2 votes
0 answers
27 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 ...
3 votes
3 answers
188 views

Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$

I recently thought of the following problem: Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$. For ...
0 votes
1 answer
87 views

How do you represent an r.e. complexity class with a list of TMs?

In this book ‘Theory of computation’ By Dexter Kozen on page 313,exercise 127 he says "A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices ...
1 vote
1 answer
34 views

Distinction between square roots in cyclic fields

Let $\mathbb{F}=\mathbb{Z}/p\mathbb{Z}$ a cyclic field. Where $p$ is fixed Let $(H)_{n\in\mathbb{N}} \in \mathbb{Z}[x_1,\dots]^{\mathbb{N}}$ a family of polynomials with $H_n\in \mathbb{Z}[x_1,\dots,...
3 votes
1 answer
287 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 ...
1 vote
1 answer
71 views

Why is infeasibility of linear programming considered to be an NP problem?

I recently came across this question, and the way I think people usually go about this is to find a certificate that answers 'yes' to the decision problem 'Is this LP infeasible?' Or, given a ...
3 votes
1 answer
51 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 $[...
2 votes
1 answer
44 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 ...
3 votes
1 answer
361 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....
1 vote
2 answers
477 views

Naive argument that P ≠ NP

Consider the following naïve argument that any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario. Let $f(x_1,x_2,\dots,x_n)$ be a Boolean function in conjunctive normal ...
-1 votes
2 answers
108 views

How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?

How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP? OR P = NP if NPC intersects with Co-NPC
1 vote
1 answer
60 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 ...
0 votes
1 answer
105 views

Transforming a Travelling Salesman Problem to a Maximum Clique Problem

Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly ...
4 votes
0 answers
49 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.
-1 votes
1 answer
44 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 ...
0 votes
1 answer
84 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^{\...
2 votes
1 answer
181 views

Constant-time adding an element?

Is a computer with infinite memory and infinite word size a Turing machine equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) if we ...
3 votes
4 answers
428 views

Undecidable problems in finite graphs

Are there any natural questions in finite graphs (or digraphs) that are undecidable?
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?
6 votes
1 answer
5k views

Proof that bin packing is strongly NP-complete?

Wikipedia claims that bin packing is strongly NP-complete. Unfortunately I haven't been able to find a proof. Does anyone know where to find it?
1 vote
1 answer
23 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 $...
1 vote
0 answers
47 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, ...
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=...
4 votes
1 answer
247 views

Simple example of exponential gap between monotone and non-monotone circuits

Is there a simple example of a monotone Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone ...
5 votes
1 answer
63 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 ...
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 ...
5 votes
0 answers
95 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$ ...
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 ...
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$. ...
1 vote
0 answers
34 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 ...
8 votes
2 answers
583 views

NP-hardness for one-dimensional facility location problem with entrance fee for each customer

We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
3 votes
1 answer
40 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 = \...
-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
4 votes
1 answer
214 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 ...
2 votes
1 answer
53 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$).
0 votes
2 answers
75 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 ...
-1 votes
3 answers
421 views

Does the use of True randomness work in this proof for P does not equal NP

To understand this proof you must first understand NP vs P problem The quantum eraser experiment True randomness Before we start I must first assert things that have been proven to be true, if you ...
0 votes
1 answer
123 views

Complexity for optimized k-sum problem

Following up on these two posts Generalised 3SUM (k-SUM) problem? https://people.csail.mit.edu/virgi/6.s078/lecture9.pdf The claim is that k-sum in the general case can be solved in $O(n^{k/2}log(n))$ ...
1 vote
2 answers
40 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
0 answers
19 views

Derivation for BNF

Given a grammar for something like: h(x) or function(x) ...
4 votes
1 answer
72 views

Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?

How can we design a data structure (storing ordered data) that gives the best worst-case lookup complexity possible, under the constraint that we require the worst-case insertion complexity to be at ...
3 votes
3 answers
970 views

P vs NP problem (Student example)

Hello dear stackexchangers, I have a simple question, and I would like to say that I am not a scientist. When I read the problem statement on this link: http://www.claymath.org/millennium-problems/p-...
1 vote
0 answers
114 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 ...
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 ...

1
2 3 4 5
110