User rus9384

8 votes

Accepted

Oracle Turing Machine EXP^EXP

answered Sep 14, 2017 at 9:16

4 votes

Unique SAT complexity clarification

answered Jun 28, 2017 at 14:00

3 votes

Accepted

General Number Field Sieve Big O Clarification

answered Jul 7, 2017 at 21:55

2 votes

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

answered Jul 17, 2017 at 0:43

2 votes

Accepted

Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

answered Aug 11, 2017 at 17:10

2 votes

Accepted

function in big O but not in little o?

answered Aug 24, 2017 at 16:59

2 votes

Accepted

Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not

answered Sep 1, 2017 at 21:44

2 votes

Is a Knapsack Problem with only Color Constraints NP-Complete?

answered Sep 11, 2017 at 22:16

2 votes

Accepted

Is the complement of MAX-CLIQUE in NP?

answered Jul 3, 2017 at 18:34

1 vote

Accepted

Complexity of $FP^{NP}$

answered Jul 4, 2017 at 11:37

1 vote

Do all NP complete problem have polynomial verifier?

answered May 19, 2017 at 7:52

1 vote

Loop invariant for a while loop

answered May 22, 2017 at 11:42

1 vote

How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time?

answered May 24, 2017 at 19:17

1 vote

Accepted

Can I prove that $\sqrt n\log{\sqrt n}=\Theta(n)$?

answered Jun 7, 2017 at 18:21

1 vote

Non-deterministic logarithmic time complexity class

answered Sep 12, 2017 at 12:05

1 vote

Locate all locations in a sorted array where arr[i]<arr[i+1]

answered Aug 24, 2017 at 2:06

1 vote

Does the 3SAT problems have to have consistent operators?

answered Nov 17, 2017 at 0:39

1 vote

What is complexity class for #XOR-2-SAT?

answered Nov 8, 2020 at 12:48

1 vote

Exponential Time Hypothesis and the input size vs number of variables

answered May 21, 2022 at 9:31

0 votes

Big o notation help?

answered Sep 18, 2017 at 2:30

0 votes

Expressing statements on elephants in propositional logic

answered Sep 27, 2017 at 22:09

0 votes

Check if $P^{NP} = P^{coNP}$

answered Aug 27, 2017 at 21:02

0 votes

Accepted

Why don't these 2 algorithms take the same time to detect duplicate lines in a file?

answered Jul 2, 2017 at 16:42

Stack Exchange Network

23 Answers

Oracle Turing Machine EXP^EXP

Unique SAT complexity clarification

General Number Field Sieve Big O Clarification

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

Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

function in big O but not in little o?

Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not

Is a Knapsack Problem with only Color Constraints NP-Complete?

Is the complement of MAX-CLIQUE in NP?

Complexity of $FP^{NP}$

Do all NP complete problem have polynomial verifier?

Loop invariant for a while loop

How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time?

Can I prove that $\sqrt n\log{\sqrt n}=\Theta(n)$?

Non-deterministic logarithmic time complexity class

Locate all locations in a sorted array where arr[i]<arr[i+1]

Does the 3SAT problems have to have consistent operators?

What is complexity class for #XOR-2-SAT?

Exponential Time Hypothesis and the input size vs number of variables

Big o notation help?

Expressing statements on elephants in propositional logic

Check if $P^{NP} = P^{coNP}$

Why don't these 2 algorithms take the same time to detect duplicate lines in a file?