Questions tagged [decision-problems]
A decision problem is a question (in some formal system) whose answer is either "yes" or "no".
3
votes
1answer
99 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
40 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
37 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
57 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
42 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
145 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
80 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
295 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
45 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
153 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
119 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
182 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(...
0
votes
1answer
84 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
471 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 ...
