mdxn
• Member for 8 years, 5 months
• Last seen more than a month ago

## 12 Answers

Accepted answer
11 votes

Computing the absolute minimal crossing number is, as you observed, $\text{NP-hard}$. The process of drawing the graphs should be at least as hard as that. The problem posed in the question is ...

View answer
Accepted answer
4 votes

I went ahead and looked to see if there was a good resource that I could provide, but beyond some resources that Aaronson wrote, I could not find any good additional supplements. You should check out ...

View answer
Accepted answer
11 votes

The concept you are looking for is called enumeration complexity, which is the study of the computational complexity of enumerating (listing) all the solutions to a problem (or the members of a ...

View answer
Accepted answer
8 votes

Regular Languages: There's some good discussion of this here: https://ell.stackexchange.com/questions/83917/how-did-regex-get-its-name Context-Free vs Context-Sensitive Grammars: For CFGs and CSGs, ...

View answer
Accepted answer
4 votes

First, let me change your definition of PP a little bit: On a YES instance, output YES with probability $\geq 1/2 + \epsilon(n)$ On a NO instance, output YES with probability $\leq 1/2 − \epsilon(n)$...

View answer
Accepted answer
3 votes

A lot of the other answers seem to be pointing in the right direction and get to the gist of things. I will give you a more pointed and concrete answer since I think it will be useful. In my opinion, ...

View answer
Accepted answer
9 votes

The term "polynomial delay", in this case, appears to refer to the time complexity of generating (or enumerating) subsequent solutions. This is a bit different than our standard notion of runtime, ...

View answer
Accepted answer
9 votes

I believe the asker is wanting to know specifically why the standard approach to reducing $\text{SAT}$ to $\text{3SAT}$ does not continue to extend to the $\text{2SAT}$ case. Here is a walkthrough as ...

View answer
Accepted answer
3 votes

I have looked into this question before and came up very short. From it, I believe that it may be the case that a cipher with this property is simply the Vernam Cipher (OTP) in disguise. It is still ...

View answer
3 votes

I am a bit uncertain by what you mean by graphical. One notion is to plot or graph a function, like $y=f(x)$, as you would in a highschool level algebra course. Another notion of "graphical" may ...

View answer
Accepted answer
2 votes

I assume that you meant to consider the difference between $BQP$ and $NP$ rather than $P$ and $NP$. $P$ is primarily only defined using deterministic time bounded Turing Machines while $BQP$ is ...

View answer
2 votes

The way your second language is written is not exactly well formed in regards to normal standards. $P$ is a set of languages and not a set of machines. Based on what you said in the rest of your ...

View answer