# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

4,499 questions
Filter by
Sorted by
Tagged with
10 views

43 views

### The subset sum problem is not in P because the question is about lossy compressed data? Why not?

Where is there a gap or error in my reasoning? The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1). The compression ...
16 views

### Douglas-Peucker line simplification algorithm time complexity

I am analyzing the time complexity of the Douglas-Peucker line simplification algorithm. Reading online I've found that it has a worst-case running time of $O(n^2)$ where $n$ is the number of points ...
30 views

### DFA for language

I want to give a DFA for the language which contains the words X ∈ {0,1,2}* for which the number of 0's + number of 1's is even AND the number of 1's + the number of 2's is odd. I tried many ...
15 views

### Are there other translations of multiplier (satisfiability) circuitry to 4 coloring?

The translation makes factorization/primality amenable to simple depth first graph coloring with 4 colors. I am mostly just wondering if it has been done before. There are zero computational ...
40 views

### Reduction from 3SAT to SUBSET-SUM

The reduction from 3SAT to SUBSET-SUM includes building a table as follows: Where base 10 representation is used for the rows in the table. I would like to know if the reduction will still be correct ...
13 views

### SAT and Polytime Reductions

If an algorithm for $SAT$ runs in $O(n^{\log n})$ time, and if $L$ belongs to $\mathsf{NP}$, is there an algorithm for $L$ that runs in $O(n^{\log n})$ time?