New answers tagged

0 votes

Can a Code Script be Optimized for Time and Space Complexity Using Logic Gates

Python is an imperative language, meaning any operation can have side effects. This makes such "gate level" thinking tricky. Its written in a way such that there's no issue with a block of ...
Cort Ammon's user avatar
  • 3,286
0 votes

Can a Code Script be Optimized for Time and Space Complexity Using Logic Gates

How much money do you have? There is at the moment no technology that could create configurable hardware that is faster than a general purpose CPU. (Improving configurable hardware would improve the ...
gnasher729's user avatar
  • 29.4k
2 votes

Is it possible to sort numbers in linear time and constant extra space?

If you require a comparison-based sorting algorithm akin to quicksort and merge sort, the answer is "No." Simply put, it can be proven that sorting an array of $n$ elements using a ...
Ziad Ismaili Alaoui's user avatar
0 votes

Is it possible to sort numbers in linear time and constant extra space?

(Note: This was posted before their edit.) Yes. Move all elements with value $-2^{31}$ to the front, order of the remaining elements doesn't matter. Easy in linear time. Then move all remaining ...
Kelly Bundy's user avatar
1 vote

PSPACE and Polynomial reduction

Correct: you can choose $C$ to be any $\text{PSPACE-complete}$ language. The only known counter-examples to this claim are ones where $C$ or $A$ are trivial, and hence, sadly, a counter-example would ...
Bader Abu Radi's user avatar
1 vote

PSPACE and Polynomial reduction

Regarding 1: choose $C = \{0x \mid x \in A \} \cup \{1x \mid x\in B\}$. Regarding $2$: $B \le_P \emptyset \implies B=\emptyset$ however $\{\varepsilon\} \le_P B \implies B \neq \emptyset$. Regarding $...
Steven's user avatar
  • 29.4k

Top 50 recent answers are included