# All Questions

47,744 questions
Filter by
Sorted by
Tagged with
17 views

33 views

### An Example of the Conjuction of Two NP-Complete Decision Problems Being Polynomial Time Solvable [duplicate]

Firstly, we define A and B as two decision problems with the same set of inputs. Define a new decision problem "A AND B" as follows: The input to "A AND B" is any valid input x for ...
23 views

### Can a problem be NP-complete and also be in complexity class FTP/XP?

P is a NPC problem. Could it be in complexity class XP/FPT or how is the relation to each other?
33 views

### Prove vertex limit for cluster editing kernel

A graph G is a cluster graph if every connected component of G is a clique. In the Cluster Editing problem, we are given as input a graph G and an integer k, and the objective is to check whether one ...
48 views

### How to modify Dijkstra's algorithm to model the path of an electric car?

I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks. Somebody online asked (but nobody ...
29 views

### Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL

I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far. Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
12 views

### Algorithm to find the number of N length sticks needed to cut into an array of various sized lengths (all <= N)

Given a length N (e.g. 20) and an array of lengths which are all <= N (e.g. [15, 1, 6]) I'd like an algorithm that finds the minimum number of N lengths necessary to be cut into the array of ...
Let $U \subset \mathbb{N}$ be a finite universe set; $B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup_{b \in B} b = U$, and if $b \in B$ then \$b \...