# Questions tagged [decision-problems]

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

23 questions
41 views

19 views

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