# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,495 questions
Filter by
Sorted by
Tagged with
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
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
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, ...
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 ...
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
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(...
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 ...
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 ...
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
34 views

1 vote
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 ...
51 views

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^{\...
181 views

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 ...
428 views

### Undecidable problems in finite graphs

Are there any natural questions in finite graphs (or digraphs) that are undecidable?
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?
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
23 views

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 ...
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 ...
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 ...
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$ ...
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
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
34 views

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
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 ...
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$).
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 ...
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 ...
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
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 ...
19 views

### Derivation for BNF

Given a grammar for something like: h(x) or function(x) ...
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 ...
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
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 ...
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 ...