Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
41 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 ...
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 ...
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
69 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 ...
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 ...
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(...
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 ...
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] \\ \...
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 ...
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 ...
2
votes
0answers
482 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 ...
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
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 (...
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 ...
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
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 ...
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 ...