Problem Detail: I’m trying to teach myself about quantum computing, and I have a decent-ish understanding of linear algebra. I got through the NOT gate, which wasn’t too bad, but then I got to the Hadamard gate. And I got stuck. Read More …
Blog
[Solved]: Does the complement of sigma Kleene star exist?
Problem Detail: If $Sigma^*$ is the set of ALL strings including the empty string, then what can its complement possibly be? The empty set? Asked By : Daniel Baughman Answered By : David Richerby Yes, the complement of all possible strings1 is no Read More …
[Solved]: why does ${a^nb^n}$ fit the pumping lemma for context-free languages?
Problem Detail: I am writing somthing about Ppumping Lemma. I know that the language $L = { a^nb^n| n ≥ 0 }$ is context-free. But I don’t understand how this language satisfies the conditions of pumping lemma (for context-free languages) ? Read More …
[Solved]: Algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality
Problem Detail: I am searching for an algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality( $text{weight}(u,v) le text{weight}(u,w) + text{weight}(w,v)$ for all vertices $u, v, w$). My first naive try was to use an algorithm for Read More …
[Solved]: Minor Mistake in Computability, Complexity, and Languages?
Problem Detail: In the book Computability, Complexity, and Languages (2nd edition), Martin Davis writes in chapter 1 (Preliminaries), section 2 (Functions): A partial function on a set $S$ is simply a function whose domain is a subset of $S$. An example Read More …
[Solved]: Is any language that can express its own compiler Turing-complete?
Problem Detail: A comment over on tex.SE made me wonder. The statement is essentially: If I can write a compiler for language X in language X, then X is Turing-complete. In computability and formal languages terms, this is: If $M$ decides Read More …
[Solved]: Example of graph with exponential many s-t minpaths and min cuts
Problem Detail: I am trying to find a graph in which both s-t minpaths and min cuts are exponential. Individually I found examples in which s-t minpaths and s-t min cuts are exponential. Can some one provide me an example of Read More …
[Solved]: If I solve hard instance, therefore I prove NP=P?
Problem Detail: If someone (off-topic) asks a question (on-topic) like this: Suppose that he claims that $mathcal{P=NP}$. Suppose that someone else (on-topic) gives him an instance of an NP-complete problem that cannot be solved by any computer optimally, i.e., to get Read More …
[Solved]: 0/1 Integer Programming and Karp’s Reduction
Problem Detail: I have been reading Karp’s famous paper on the NP-Completeness of different problems, Reducibility among combinatorial problems, and I have a question on the reduction from SAT to 0/1 Integer Programming defined there. The problem 0/1 Integer Programming is Read More …
[Solved]: How to use Artificial Intelligence in Computer Chess
Problem Detail: In some (historical) papers, chess has been referred to as the drosophila of artificial intelligence. While I suppose that in current research, the mere application of a search algorithm is at best advanced computer science, I believe that there Read More …
