Questions tagged [decision-problems]

A decision problem is a question (in some formal system) whose answer is either "yes" or "no".

23 questions
688 views

Characterisation of linearly separable points of a hypercube

Essentially, linearly separable points are just those corners that can be cut off with just one slice as marked out by a hyperplane. E.g. for a cube, the following 4 points (red) are not linearly ...
1k views

How to determine whether a system of linear inequalities has a positive solution or not?

How to determine whether a system of linear inequalities has a positive solution or not? Is there any poly-time algorithm to do this? Or the best algorithms known are no less complex than algorithms ...
103 views

28 views

88 views

Determine feasibility of a linear system of inequalities

This sounds like a famous and straightforward question, but I do not know how exactly to solve it, although I have some rather half-baked ideas. I have already looked at these two answers, this and ...
183 views

2-Colorable & Decision Problem

Consider the following decision problem. Given $m$ subsets $A_{1}, \dots , A_{m} \subset \{1 , \dots , n \}$. Does there exist a subset $S \subset \{ 1, \dots ,n \}$ such that the cardinality of the ...