mdxn
  • Member for 8 years, 4 months
  • Last seen more than a month ago
How to reduce the number of crossing edges in a diagram?
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
Complexity classes pertaining to listing all solutions?
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
What is "polynomial delay?"
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
SAT not reducible to 2SAT
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
How did each class of languages receive their name?
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
Post-selection and complexity theory
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
A clarification on $PP$
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
How can I prepare for CS in university
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
Perfectly Secure Ciphers known other than the OTP
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
What does it mean to multiply or divide polynomials?
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
Are there problems that are polynomial-time equivalent to factoring composites?
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
Machines in P undecidable?
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