Farewell Stack Exchange
  • Member for 4 years, 7 months
  • Last seen more than 3 years ago
1 answers
6 votes
302 views
2 bookmarks
Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?
1 answers
6 votes
271 views
3 bookmarks
Can deterministic Turing machine beats/wins (if possible) the "Bombs and Levers" game in polynomial time?
1 answers
3 votes
192 views
1 bookmarks
Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?
1 answers
2 votes
279 views
1 bookmarks
Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?
1 answers
2 votes
207 views
1 bookmarks
Does an algorithm with complexity $\Theta(2^\sqrt{n})$ to solve any NP problem count as "good" and practical as any other polynomial algorithm?
1 answers
2 votes
66 views
2 bookmarks
What is the complexity to show this theorem?
1 answers
2 votes
157 views
1 bookmarks
What is the set of all maximal 3CNF formulas?
1 answers
2 votes
228 views
2 bookmarks
What is the set of all minimal 3CNF formulas?
1 answers
2 votes
343 views
1 bookmarks
Is computing the cardinality of sum of regular expressions without kleene star closure EXPTIME problem?
1 answers
2 votes
520 views
1 bookmarks
Complexity of simplifying two-variable algebraic expression
4 answers
1 votes
1k views
2 bookmarks
Is this possible to solve 3SAT in O(n^24) time and O(1) space?
1 answers
1 votes
751 views
1 bookmarks
What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable?
1 answers
1 votes
721 views
1 bookmarks
Is this possible to solve boolean satisfiablility by using karnaugh maps to simplify the whole given boolean formula by simplifying subformulas?
1 answers
1 votes
727 views
1 bookmarks
Convert conjunctive normal form to equivalent boolean formula with only NAND gates
1 answers
1 votes
48 views
1 bookmarks
What is the largest possible minimal 3CNF formula as function of the number of variables?
1 answers
1 votes
237 views
1 bookmarks
Does exist an algorithm to find all equivalence classes of given regular expression without kleene star? If yes then what is it?
1 answers
1 votes
958 views
1 bookmarks
Is this possible to solve SAT in polynomial time by reducing it to the problem of solving system of nonlinear equations?
1 answers
1 votes
574 views
1 bookmarks
Is this possible to solve 4SAT in polynomial time?
1 answers
1 votes
146 views
Can quantum computer compute the minimal intersection DFA of numerous minimal DFAs in polynomial time using polynomial number of qubits?
3 answers
1 votes
532 views
2 bookmarks
What is the space in big-O notation of the minimal DFA accepting the intersection of two finite languages where their minimal DFAs are given
1 answers
0 votes
113 views
1 bookmarks
Is my problem NP-Hard?
0 answers
0 votes
59 views
1 bookmarks
What is the complexity of my algorithm to solve this kind of system of nonlinear equations?
1 answers
0 votes
84 views
1 bookmarks
Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula
0 answers
0 votes
130 views
1 bookmarks
Convert conjunctive normal form to equivalent boolean formula with only NOR gates
1 answers
0 votes
654 views
1 bookmarks
What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?
0 answers
0 votes
110 views
1 bookmarks
Is the algorithm to solve 4SAT correct and what it's both time and space complexity?
1 answers
0 votes
230 views
1 bookmarks
Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars?
1 answers
-1 votes
59 views
1 bookmarks
Is this possible to find the maximum of differentiable and analytic function on finite and fixed interval in O(1) time using quantum computer?
1 answers
-1 votes
241 views
1 bookmarks
What is the time and space complexity of the algorithm to either prove or refute that given expression is equals to (A+B)^n for any natural number n