# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,493 questions
Filter by
Sorted by
Tagged with
1 vote
31 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: \...
• 111
1 vote
14 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 ...
• 455
390 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 ...
• 3,972
18 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 ...
• 51
1 vote
52 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, ...
28 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 ...
28 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,684
98 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 ...
290 views

• 161
46 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 ...
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....
• 425
53 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.
• 41
1 vote
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 ...
• 433
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 ...
• 101
86 views

1 vote
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, ...
• 11
43 views

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

### Derivation for BNF

Given a grammar for something like: h(x) or function(x) ...
• 11
42 views

1 vote
115 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 ...
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 ...
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: ...
• 101
1 vote
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$ ...
• 1,684
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 ...
• 103
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)$ ...
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 ...
96 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) { ...
1 vote