Questions tagged [decision-problems]
A decision problem is a question (in some formal system) whose answer is either "yes" or "no".
0
votes
2answers
41 views
Is this expected utility correct?
I'm learning Bayesian Networks and Decision Making but I'm not very good with notation.
I have written down this expected utility (more info here):
$$UE=\sum_s\max_b\sum_{s,r}\max_q\sum_tP(t)P(s|t)P(...
1
vote
0answers
28 views
What is the meaning of Motzkin's theorem?
Theorem: Let $A$ and $C$ be two matrices. The system of linear inequalities $Ax<0$ and $Cx \leq 0$ has a solution iff the following equation in $\lambda$ and $\mu$ does not have a solution$$A^T \...
0
votes
0answers
19 views
How to calculate pi sub D, upper opt
I¡m learning Bayesian Networks and now I'm studying Decision Making.
I have the following probability table (sorry about the format, I don't know how to do it better):
________| $\psi(y,t,d)$
$+y,+t,...
0
votes
0answers
40 views
A person often finds that she is up to 1 hour late for work. A decision problem
A person often finds that she is up to 1 hour late for work.
If she is from $1$ to $30$ minutes late, $\$4 $ is deducted from her paycheck;
if she is from $31$ to $60$ minutes late for work, $\$8$ is ...
0
votes
1answer
59 views
How to check if a point is within a convex hull?
BACKGROUND
I'm working on a physics problem whereby I want to check whether a vector $\vec{v}$ of $D \in \mathbb{N}$ measurements $v_d \in [-1, 1]$, $d \in \{1, \cdots, D\}$ can result from the ...
1
vote
0answers
36 views
How to determine whether a given point lies inside or outside of a triangle in 3D?
For example if i have triangle defined by following points
[A=(15.0, 14, 15.0), B=(15.0, -45, 15.0), C=(-15.0, 14, 15.0)], and consider the point need to be project p=(15,78,0). I want to determine, ...
3
votes
1answer
103 views
Decision procedure on linear transformations of integer vectors.
I have an linear transformation of $k$-vectors of integers, $T$, and a vector of integers $v$. I would like to determine if there is some $n$ such that $T^nv$ is a vector that starts with zero.
$$
\...
1
vote
1answer
66 views
Using the reduction of 3-SAT to 3-COLOR, explain why complexity proofs by reduction work.
I'm reading about the proof that 3-COLOR is in NP-Hard, by reduction of 3-SAT to 3-COLOR (as listed here for example: http://cs.bme.hu/thalg/3sat-to-3col.pdf). And here's a passage from Wikipedia, ...
3
votes
0answers
41 views
How to quickly determine if a linear program is feasible?
I have a series of linear programs in canonical form
$$\begin{array}{ll} \text{maximize} & c^T \mathrm x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$
and I need to ...
0
votes
1answer
62 views
Weakened versions of Word and Isomorphism Problems in group theory
Here are my questions:
(Weakened Word Problem) Let $\langle X |R\rangle$ be a finite presentation of a group $G$, and let $w$ be an element of the free group $F(X)$. Does there exist an algorithm (...
0
votes
1answer
43 views
Nonempty interior is equivalent to the feasibility of set of strict quadratic inequalities. Why?
From Convex Optimization:
Let $E_i = \{x \mid f_i(x) \le 0\}$ where $f_i(x) = x^TA_ix + 2b_i^Tx +
c_i$ for $ i = 1, 2, \dots, m$ and $A_i \in S^n_{++}$ where $S^n_{++}$
is the set of all ...
3
votes
1answer
152 views
Properly stating a decision problem for a Hamiltonian cycle problem
I'm running an algorithms seminar and I'm trying to express the Hamiltonian cycle problem in a new way that is exciting to students. I know that many of them play a game called Hearthstone and I'm ...
0
votes
1answer
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 ...
1
vote
1answer
301 views
What is the definition of the complement of a decision problem?
I am trying to understand the definition of the complement of a decision problem.
The reason is because it is the core issue that is stopping me from understanding why SAT is the complement of ...
0
votes
0answers
46 views
Computational complexity of a feasibility LP with $m$ inequalities, in $d$ dimension?
How would you quantify the computational complexity of feasibility LPs?
Say, for example, an LP with $m$ inequalities:
$$
\begin{cases}
\mathbf{a_i} \cdot \mathbf{x} \leq b_i, \quad i \in [m] \\
\...
2
votes
1answer
157 views
A decision problem that is Cook-reducible to its complement
I'm taking an algorithms course and we are covering polynomial time reductions, and I've read online that many decision problems are polynomial-time reducible to their complements.
Can anyone give ...
0
votes
2answers
124 views
An algorithm to decide whether a polyhedron is a subset of another polyhedron
I've encountered the following question which I am unable to solve:
Given
$$P = \{\vec x \mid A\vec x \geq \vec a\}$$
$$Q = \{\vec x \mid B\vec x \geq \vec b\}$$
where $P, Q \...
0
votes
1answer
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 ...
1
vote
2answers
93 views
How to determine this?
For any $6$ coplanar points
$$\left(x_{1}+y_{1},x_{2}+y_{2},x_{3}+y_{3}\right)$$
$$\left(x_{1}+y_{2},x_{2}+y_{1},x_{3}+y_{3}\right)$$
$$\left(x_{1}+y_{3},x_{2}+y_{2},x_{3}+y_{1}\right)$$
$$\left(...
6
votes
1answer
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 ...
0
votes
1answer
88 views
Determining if a point in 3-space is inside a polytope knowing only the distances to the polytope's vertices
If I have a point in 3-space, as well as a convex 3-polytope, and an unordered set of distances to the vertices of the 3-polytope (but not the position of these vertices) is there any way for me to ...
2
votes
0answers
481 views
Determine if a polyhedron is a polytope
Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron.
Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
4
votes
1answer
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 ...
