Stack Exchange

Steven

https://www.isnphard.com

An approximation of a Turing machine

top accounts reputation activity subscriptions
Top Questions
Top Answers
29
Data structure for fast insertion and fast random element removal
cs.stackexchange.com

23
Algorithm for merging arrays while keeping their order
cs.stackexchange.com

22
Are all Integer Linear Programming problems NP-Hard?
cs.stackexchange.com

17
How is the problem, {⟨G⟩|G has no triangle} in Logspace?
cs.stackexchange.com

17
Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ regular or not?
cs.stackexchange.com

14
Time Complexity of Linear Search vs Brute Force
cs.stackexchange.com

14
Can any problem in P be converted to any other problem in P in polynomial time?
cs.stackexchange.com

12
Proof that for 2n nodes of +1 and -1 position doesn't count
cs.stackexchange.com

12
I have found an example where regular expression is not closed under concatenation. Where am I wrong?
cs.stackexchange.com

11
Are there problems in NP that do not reduce in polynomial time to any problem in NP?
cs.stackexchange.com

10
Why does the order of the nested loops matter when solving the Coin Change problem?
cs.stackexchange.com

9
Find the number using binary search against one possible lie
cs.stackexchange.com

8
Two regular languages over the same alphabet, regular or not regular?
cs.stackexchange.com

8
What are you allowed to move into the big O notation for it to be still correct?
cs.stackexchange.com

7
Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?
cs.stackexchange.com

7
Proof that $P\subseteq NP$ without nondeterministic TM
cs.stackexchange.com

7
Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$
cs.stackexchange.com

7
Faster algorithm for a specific inversion
cs.stackexchange.com

6
NP-completeness of problem based on non-arbitrary instance
cs.stackexchange.com

6
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
cs.stackexchange.com

6
Why can't $QBF$ be reduced to $SAT$
cs.stackexchange.com

6
Topological sort with minimum maximal distance in array
cs.stackexchange.com

6
how can turing machines be universal models of computation if they can't perform binary search?
cs.stackexchange.com

6
Test if $ \sum_{n=0}^\infty \frac{n^2}{2^n} $ = O(1)
cs.stackexchange.com

6
Why does the Huffman coding algorithm produce a valid tree?
cs.stackexchange.com

6
Is this clique algorithm in polynomial time correct or might it have another time complexity?
cs.stackexchange.com

6
Diameter of a disconnected graph
cs.stackexchange.com

6
Does this argument prove CFLs are not closed under union?
cs.stackexchange.com

6
Can Turing Machines solve non-decision problems?
cs.stackexchange.com

5
Index variable takes up log(n) space?
cs.stackexchange.com

1 2