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".

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 ...