Skip to main content
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
325 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
286 views

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

1 vote
1 answer
305 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
309 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
51 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
52 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
53 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
57 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
185 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
252 views

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