Problem Detail: I’m looking for a proof to the claim stated in the title: if $Lin NPcap Co-NP$ is $NP$-Hard, then $NP=Co-NP$. I read the proof from my professor’s recitation, but couldn’t understand it, and I was hoping to find more Read More …
Blog
[Solved]: Proof of Dijkstra Algorithm Optimality
Problem Detail: Has it been proven that Dijkstra’s algorithm is optimal for asymptotic worst case of single-source shortest path on directed graphs? (Assume no preprocessing) I became curious when Wikipedia mentioned it as the ‘best known’ rather than the ‘best possible’. Read More …
[Solved]: NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round)
Problem Detail: The Google Hash Code 2015 Test Round (problem statement) asked about the following problem: input: a grid $M$ with some marked squares, a threshold $T in mathbb{N}$, a maximal area $A in mathbb{N}$ output: the largest possible total area Read More …
[Solved]: Speed-up of two-tape Turing machine
Problem Detail: I try to figure out linear speed-up of Turing machine. Prove that any problem that can be solved by a two-tape Turing machine that has time complexity t can be solved by another two-tape Turing machine having time complexity Read More …
[Solved]: Difference between time complexity and computational complexity
Problem Detail: For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm. Asked By : Median Read More …
[Solved]: Is language equality for linear context-free grammars decidable?
Problem Detail: Let’s consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent? In general, this problem is undecidable. However, if both $G_1$ and $G_2$ are left-linear (or Read More …
[Solved]: Identifying events related to dates in a paragraph
Problem Detail: Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph? Example, consider the following paragraph: In June 1970, the great leader took the oath. But it was only Read More …
[Solved]: Does the ‘difference’ operation add expressiveness to a query language that already includes ‘join’?
Problem Detail: The set difference operator (e.g., EXCEPT in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases that do not support the set difference operator directly, but which support LEFT JOIN Read More …
[Solved]: Finding an Uncomputable Function
Problem Detail: Let there be 2 sets $X$ and $Y$, both are countable (assume the bijection from $mathbb{N}$ to the respective sets is computable) and infinite. Let $S$ be the set of all possible functions (NOT necessarily computable, i dont care Read More …
[Solved]: Is this phrase structure grammar from my textbook correct?
Problem Detail: I just started reading “Parsing Techniques, A Practical Guide”, Second Edition, by Dick Grune and Ceriel J.H. Jacobs. On page 12, the authors start describing a set of rules that can be used to generate the set of all Read More …
