Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Farewell Stack Exchange's user avatar
Farewell Stack Exchange's user avatar
Farewell Stack Exchange's user avatar
Farewell Stack Exchange
  • Member for 6 years, 11 months
  • Last seen more than 1 year ago
6 votes
1 answer
323 views

Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

6 votes
1 answer
289 views

Can deterministic Turing machine beats/wins (if possible) the "Bombs and Levers" game in polynomial time?

4 votes
1 answer
307 views

Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?

2 votes
1 answer
283 views

Does an algorithm with complexity $\Theta(2^\sqrt{n})$ to solve any NP problem count as "good" and practical as any other polynomial algorithm?

2 votes
1 answer
463 views

Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?

2 votes
1 answer
328 views

What is the set of all minimal 3CNF formulas?

2 votes
1 answer
797 views

Complexity of simplifying two-variable algebraic expression

2 votes
1 answer
427 views

Is computing the cardinality of sum of regular expressions without kleene star closure EXPTIME problem?

2 votes
1 answer
203 views

What is the set of all maximal 3CNF formulas?

2 votes
1 answer
85 views

What is the complexity to show this theorem?

2 votes
1 answer
1k views

Convert conjunctive normal form to equivalent boolean formula with only NAND gates

1 vote
1 answer
1k views

What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable?

1 vote
1 answer
2k views

Is this possible to solve SAT in polynomial time by reducing it to the problem of solving system of nonlinear equations?

1 vote
1 answer
323 views

Does exist an algorithm to find all equivalence classes of given regular expression without kleene star? If yes then what is it?

1 vote
1 answer
127 views

What is the largest possible minimal 3CNF formula as function of the number of variables?

1 vote
1 answer
1k views

Is this possible to solve boolean satisfiablility by using karnaugh maps to simplify the whole given boolean formula by simplifying subformulas?

1 vote
1 answer
180 views

Can quantum computer compute the minimal intersection DFA of numerous minimal DFAs in polynomial time using polynomial number of qubits?

1 vote
3 answers
750 views

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 vote
1 answer
686 views

Is this possible to solve 4SAT in polynomial time? [closed]

1 vote
4 answers
2k views

Is this possible to solve 3SAT in O(n^24) time and O(1) space?

0 votes
0 answers
60 views

What is the complexity of my algorithm to solve this kind of system of nonlinear equations?

0 votes
1 answer
125 views

Is my problem NP-Hard?

0 votes
0 answers
252 views

Horn Satisfiability is NP Complete, isn't it?

0 votes
1 answer
120 views

Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula

0 votes
0 answers
144 views

Is the algorithm to solve 4SAT correct and what it's both time and space complexity?

0 votes
1 answer
251 views

Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars?

0 votes
1 answer
829 views

What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?

0 votes
0 answers
153 views

Convert conjunctive normal form to equivalent boolean formula with only NOR gates

-1 votes
1 answer
260 views

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 [closed]

-1 votes
1 answer
73 views

Is this possible to find the maximum of differentiable and analytic function on finite and fixed interval in O(1) time using quantum computer?