rus9384's user avatar
rus9384's user avatar
rus9384's user avatar
rus9384
  • Member for 6 years, 4 months
  • Last seen more than a month ago
1 vote

Exponential Time Hypothesis and the input size vs number of variables

1 vote

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

1 vote

Does the 3SAT problems have to have consistent operators?

0 votes

Expressing statements on elephants in propositional logic

0 votes

Big o notation help?

8 votes
Accepted

Oracle Turing Machine EXP^EXP

1 vote

Non-deterministic logarithmic time complexity class

2 votes

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

2 votes
Accepted

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

0 votes

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

2 votes
Accepted

function in big O but not in little o?

1 vote

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

2 votes
Accepted

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

2 votes

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

3 votes
Accepted

General Number Field Sieve Big O Clarification

1 vote
Accepted

Complexity of $FP^{NP}$

2 votes
Accepted

Is the complement of MAX-CLIQUE in NP?

0 votes
Accepted

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

4 votes

Unique SAT complexity clarification

1 vote
Accepted

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

1 vote

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

1 vote

Loop invariant for a while loop

1 vote

Do all NP complete problem have polynomial verifier?