Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
Jesus is Lord's user avatar
Jesus is Lord's user avatar
Jesus is Lord's user avatar
Jesus is Lord
  • Member for 8 years, 7 months
  • Last seen more than a month ago
4 votes
4 answers
3k views

Is $Ω(n\log ⁡n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?

3 votes
1 answer
322 views

Why doesn't descriptive complexity theory solve P = NP?

3 votes
2 answers
1k views

Is it always possible to order grammar rules so that all the symbols on the left will be contained on the right in a previous rule?

2 votes
0 answers
79 views

Can all of math be automated?

2 votes
0 answers
33 views

Do undecidable problems have no HO query? If so, could I have an example?

2 votes
1 answer
285 views

Would a sparse NP-Complete language imply L = NP?

1 vote
1 answer
299 views

Could the halting problem in theory be solved for any finite set of Turing Machines?

1 vote
1 answer
78 views

Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists?

1 vote
1 answer
36 views

Does checking the middle bit of an input require a log(n) space pointer? (Reusing space)

1 vote
1 answer
305 views

Are there NP languages whose verification is P-complete?

1 vote
1 answer
59 views

What complexity class is this set of grammars?

1 vote
1 answer
118 views

What complexity class is this set of grammars? In between NL and P?

1 vote
1 answer
100 views

Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?

0 votes
1 answer
49 views

What is the time complexity of a Turing Machine that iterates through each prime number from 2 to K (assume oracle generates the next prime)?

0 votes
1 answer
50 views

Proving grammar equivalence in simple grammar (generate any sequence of three characters)

0 votes
1 answer
43 views

What context-free grammar recognizes a list of numbers 1 - N in order?

0 votes
1 answer
51 views

Given a graph `G`, what is the maximum number of "minimum" cycles it could have?

0 votes
1 answer
32 views

What complexity class is this set of grammars? RE?

0 votes
1 answer
30 views

Can uniqueness of strings (each with an equal number of 1's and 0's) be decided in logspace?

0 votes
1 answer
56 views

Does checking the middle bit of an input require a log(n) space pointer?

0 votes
1 answer
66 views

If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?

0 votes
2 answers
184 views

Are NP proofs limited to polynomial length?

0 votes
1 answer
26 views

Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?

0 votes
1 answer
104 views

What complexity class does is this set of grammars? NL-complete?

-1 votes
1 answer
251 views

When does Gaussian elimination solve exact 1-in-3 SAT?