Problem Detail: What I’m trying to do is to show a problem in NP can be reduced to the min weight vertex cover problem I’ve chosen the max independent weight problem = input: A graph G with weights on each vertex, Read More …
Blog
[Solved]: If the decision problem can be solved in poly time, show the optimization problem also can
Problem Detail: Here is a problem I am trying to solve: The bin packing decision problem is defined as follows: given an unlimited number of bins, each of capacity equal to $1$, and $n$ objects with sizes $s_1$, $s_2$, $dots$, $s_n$ Read More …
[Solved]: showing that the pair of Finite Automata are equivalent
Problem Detail: Here I am trying to show that the pair of Finite Automata are equivalent. I have tried something but I am not sure if I am in the right direction. This is what I have. These are pairs of Read More …
[Solved]: Complexity of transposing matrices represented as list of row or column vectors
Problem Detail: Given [[1,4,7],[2,5,8],[3,6,9]] which is a list of the column vectors of matrix |1, 2, 3| |4, 5, 6| |7, 8, 9| is $ Omega(n^2) $ a lower bound for transposing? Assume the matrix is not always square. I have Read More …
[Solved]: Count number of special onto functions
Problem Detail: We define an onto function from $[n] times [n]$ to $[n-2] cup {0}$ as follows, where $[n] = {1,2,3,ldots ,n}$, $$f : [n] times [n] rightarrow [n-2] cup {0}.$$ 1) $f(x,x) = 0$. 2) $f(x,y) = f(y,x) > 0$, Read More …
[Solved]: What is the decidable language in $P/poly$ but not in $P$?
Problem Detail: Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$ Asked By : user6818 Answered By : Yuval Filmus Take a language $L$ which is not in $mathsf{E} = bigcup_{c=1}^infty mathsf{TIME}(2^{cn})$. Read More …
[Solved]: A puzzle related to nested loops
Problem Detail: For a given input $N$, how many times does the enclosed statement executes? for $i$ in $1ldots N$ loop $quad$for $j$ in $1ldots i$ loop $quad$$quad$for $k$ in $ildots j$ loop $quad$$quad$$quad$$sum = sum + i$ ; $quad$$quad$end loop; Read More …
[Solved]: If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?
Problem Detail: I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it will mean that all problems in NP can Read More …
[Solved]: Difficult Question to Understand (Computer Artitechture)
Problem Detail: You are designing an elevator controller for a building with 25 floors. The controller has two inputs: UP and DOWN. It produces an output indicating the floor that the elevator is on. There is no floor 13. What is Read More …
[Solved]: How can I show a linear languages are closed against concatenating with regular ones?
Problem Detail: This was given as a homework problem but I have already submitted the assignment. I’d like to resolve it at this point for my own satisfaction. Given that $L_1$ is a linear language and $L_2$ is a regular language, Read More …
