Problem Detail: Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C_i$ from a $SAT$ instance containing more than 3 literals to a $3-SAT$ instance is done this way, Suppose $C_1$ is ${x_1, x_2, x_3, x_4}$. It’s equivalent representation Read More …
Category: Uncategorized
[Solved]: Regularity of unary languages with word lengths the sum of two resp. three squares
Problem Detail: I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally: $$L_k={a^nmid n=sum_{i=1}^k {n_i}^2,;;n_iinmathbb{N_0};(1le ile k)} $$ It is easy to show that $L_1={a^{n^2}mid ninmathbb{N_0}}$ is not regular Read More …
[Solved]: Could an NP-hard problem have a mechanical or physical solution method?
Problem Detail: Is there any NP-hard problem that we can find a mechanical “polynomial time” solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we can move water. If this Read More …
[Solved]: Single-source shortest paths as a linear program
Problem Detail: I saw that I can formulate single-source shortest path as the following linear program: Given $G=(V,E)$ and $wcolon Eto R$ and with negative cycles, find $max,d(s,t)$ such that begin{align*} d(s,v) &le d(s,u)+w(u,v) quad forall (u,v)in E d(s,s) &=0 end{align*} Read More …
[Solved]: Want to know the time complexity inner for loop which is partially iterating the array
Problem Detail: Question: Find out next increasing value of each element in this below array. int[] array = { 5, 2, 7, 10, 4, 12} e.g) 5’s nextIncreasingValue: 7 2’s nextIncreasingValue: 7 7’s nextIncreasingValue: 10 … 12’s nextIncreasingValue: -1 Implementation: for(int Read More …
[Solved]: Expressive power of lexer + parser
Problem Detail: Most modern compilers split their syntax analysis into a lexical phase that is followed by a parsing phase. The lexical phase is given by a regular expression, while parsing is guided by a context-free grammar. What class of languages Read More …
[Solved]: How is IO a monad?
Problem Detail: I am learning the Haskell programming language. From what I am reading, Input/Ouput (IO) raises challenges for Haskell’s purity, since by definition we are interacting with the outside world. From Wikipedia: In a purely functional language, such as Haskell, Read More …
[Solved]: Are randomized algorithms constructive?
Problem Detail: From , the proofs by the probabilistic method are often said to be non-constructive. However, a proof by probabilistic method indeed designs a randomized algorithm and uses it for proving existence. Quoted from p103 of Randomized Algorithms By Rajeev Read More …
[Solved]: Inapproximability result implies apx-hardness?
Problem Detail: If an optimization problem is known to be inapproximable up to some precision, does this automatically imply that the problem is apx-hard? Asked By : mat Answered By : Yuval Filmus If P$=$NP then there is a polytime algorithm for any Read More …
[Solved]: Is there a simple example of sets such that $A leq_T B$ but not $A leq_m B$?
Problem Detail: I wonder if there is a simple example of sets $A$ and $B$ such that $A$ is Turing-reductible to $B$ but not many-to-one reductible to $B$. Asked By : pintoch Answered By : Martin Jonáš For example sets $H = {x Read More …
