Problem Detail: I want to know if this problem is polynomial-time solvable or not? The problem is: Given a nonnegative integer-valued matrix of size $2times n$ and two nonnegative integer numbers $b<n$ and $c$. The question is: Find a subset of Read More …
Blog
[Solved]: Construction of fair teams
Problem Detail: let’s say we have a set of players that we want to match into teams of aproximatly same strength, so that no team is much stronger than another team. Each team consists of two players. One player is taking Read More …
[Solved]: Brzozowski algebraic method for NFA
Problem Detail: Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA some nodes have multiple in/outgoing edges single start state there might be multiple final states a state can contain self loops where Read More …
[Solved]: Enumerating sets in a random order
Problem Detail: I have multiples arrays. I’d like to enumerate all sets containing exactly one item from each array in a (pseudo-)random order, without explicitly building the array of all sets. Any solution, even with poor pseudo-randomization, is welcome. EDIT: Example Read More …
[Solved]: Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?
Problem Detail: The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there’s no obvious way to verify a proposed solution of the optimization problem in polynomial time. But is there a Read More …
[Solved]: Lambda Calculus Evaluation
Problem Detail: I know this is a simple question but can someone show me how $(lambda y. lambda x. lambda y.y) (lambda x. lambda y. y)$ reduces to $lambda x. lambda y. y$. Asked By : prerm2686 Answered By : sepp2k The reason Read More …
[Solved]: Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?)
Problem Detail: I’ve been trying to wrap my head around Co-NP, and how it’s different to NP, but I am having some trouble. Co-NP is defined by Wikipedia as this: “A decision problem $mathcal{X}$ is a member of co-NP if and Read More …
[Solved]: Running time analysis of a segment tree
Problem Detail: Can someone provide an analysis of the update and query operations of a segment tree? I thought of a way which goes like this – At every node, we make at most two recursive calls on the left and Read More …
[Solved]: How to prove that ε-loops are not necessary in PDAs?
Problem Detail: In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a proof that uses only automata; therefore, Read More …
[Solved]: Supporting queries for finding how many intervals in a dynamic set of 1D intervals contain a given point
Problem Detail: You want to create a data structure that can store 1 dimensional intervals and also support the query for finding the total amount of intervals intersecting a given point. One solution would be for each query to scan through Read More …
