Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [space-complexity]

Space complexity describes the amount of memory space required by a deterministic Turing machine to solve a given computational problem with a certain algorithm. If necessary, also use the [memory-space] tag.

6
votes
1answer
160 views

Can we use quantum machines to reduce space complexity of deterministic turing machines?

Can we convert every algorithm in $\text{P}$ (polynomial time complexity for deterministic machines) into a quantum algorithm with polynomial time and $O(\log n)$ quantum bit?
2
votes
1answer
166 views

Is there a polynomial quantum algorithm for graph coloring?

Is there a polynomial time and polynomial space quantum algorithm for finding a 4 colouring of any loopless planar graph?