User Farewell Stack Exchange

6 votes

1 answer

324 views

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

asked Jun 17, 2017 at 20:55

6 votes

1 answer

290 views

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

asked Jul 19, 2017 at 1:30

4 votes

1 answer

320 views

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

asked Aug 12, 2017 at 17:46

2 votes

1 answer

284 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?

asked Aug 12, 2017 at 19:49

2 votes

1 answer

482 views

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

asked Aug 18, 2017 at 15:20

2 votes

4 answers

2k views

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

asked Jul 16, 2017 at 23:14

2 votes

1 answer

333 views

What is the set of all minimal 3CNF formulas?

asked Jul 17, 2017 at 20:39

2 votes

1 answer

817 views

Complexity of simplifying two-variable algebraic expression

asked Jul 11, 2017 at 15:53

2 votes

1 answer

429 views

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

asked Jul 23, 2017 at 18:06

2 votes

1 answer

204 views

What is the set of all maximal 3CNF formulas?

asked Jul 26, 2017 at 16:53

2 votes

1 answer

88 views

What is the complexity to show this theorem?

asked Jul 26, 2017 at 19:47

2 votes

1 answer

1k views

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

asked Aug 5, 2017 at 15:51

1 vote

1 answer

1k views

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

asked Jul 22, 2017 at 19:44

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?

asked Jul 27, 2017 at 0:34

1 vote

1 answer

330 views

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

asked Jul 27, 2017 at 20:58

1 vote

1 answer

130 views

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

asked Aug 2, 2017 at 19:38

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?

asked Aug 4, 2017 at 8:57

1 vote

1 answer

192 views

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

asked Jul 12, 2017 at 13:05

1 vote

3 answers

755 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

asked Jul 9, 2017 at 2:31

1 vote

1 answer

695 views

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

asked Jul 18, 2017 at 8:43

0 votes

0 answers

145 views

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

asked Jul 20, 2017 at 19:31

0 votes

1 answer

252 views

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

asked Jul 10, 2017 at 23:03

0 votes

1 answer

836 views

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

asked Jul 23, 2017 at 2:49

0 votes

0 answers

154 views

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

asked Aug 6, 2017 at 16:02

0 votes

1 answer

122 views

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

asked Aug 18, 2017 at 22:46

0 votes

0 answers

60 views

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

asked Aug 20, 2017 at 13:57

0 votes

1 answer

125 views

Is my problem NP-Hard?

asked Aug 30, 2017 at 19:54

0 votes

0 answers

269 views

Horn Satisfiability is NP Complete, isn't it?

asked Jun 10, 2022 at 11:32

-1 votes

1 answer

74 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?

asked Aug 19, 2017 at 21:06

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

asked Jul 13, 2017 at 17:35

Stack Exchange Network

30 Questions

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

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

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

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

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

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

What is the set of all minimal 3CNF formulas?

Complexity of simplifying two-variable algebraic expression

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

What is the set of all maximal 3CNF formulas?

What is the complexity to show this theorem?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Is my problem NP-Hard?

Horn Satisfiability is NP Complete, isn't it?

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

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]