Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

1
vote
0answers
233 views

approximate solution for bin packing problem that minimizes sum of max values of bins

I am trying to approximate the following NP-hard problem, which is similar to bin packing, but does not have a linear objective function: minimize $\Sigma_{i=1, \ldots, W}$ max{$v_s$ | s $\in$ ...
0
votes
3answers
83 views

Binary expansions associated with languages

Let $\mathbf{L}$ be the set of all languages over $\Sigma=\{0,1\}$ and $E(\Sigma)$ be a lexicographic enumeration of $\Sigma^*$. Then there exists a bijection from $f:\mathbf{L} \rightarrow [0,1)$ ...
16
votes
2answers
1k views

What is the complexity of succinct (binary) Nurikabe?

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid to be filled with on/off values for each cell, with each number indicating a ...
25
votes
2answers
2k views

Is factoring polynomials as hard as factoring integers?

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard? One thing I ...
9
votes
2answers
708 views

Has there been a rigorous analysis of Strassen's algorithm?

According to Wikipedia, Strassen's Algorithm runs in $O(N^{2.807})$ time. Has anyone seen a more rigorous analysis displaying constants, possibly in a specific language such as C or Java? I ...
1
vote
3answers
421 views

Can we partition NP-complete problem into finite number of polynomially solvable problems?

I have asked this question on cstheory. Let $\Pi$ be NP-complete problem. Can we partition the set of instances of $\Pi$ into finite number of subsets (subproblems) each of which is polynomially ...
27
votes
1answer
2k views

$e^{e^{e^{79}}}$ and ultrafinitism

I was reading the following article on Ultrafinitism, and it mentions that one of the reasons ultrafinitists believe that N is not infinite is because the floor of $e^{e^{e^{79}}}$ is not computable. ...
2
votes
1answer
1k views

Gauss Jordan elimination - count of steps for $N \times M$ equation

I am having some problem wrapping my head around an assignment. I have to find out how many additions, subtractions, multiplications and divisions are used while solving an $N \times M$ linear ...