# Questions tagged [decision-problems]

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

100 questions
Filter by
Sorted by
Tagged with
33 views

150 views

### Game with Poisson distribution

Problem introduction Let us consider the following problem. We have 2 players Alice and Bob and they play a game which is about getting points. The player with most points wins. The points player get ...
39 views

### Can I still use the value iteration to deal with continuous state-space MDP with piecewise value function?

I'm now working on a maintenance optimization problem, and I'm learning to use MDP for model formulation. The state space concerned is continuous, but the value function is actually piecewise. For ...
1 vote
152 views

### Link between all NP-complete problems

I have heard a quiet large number of times that "If a polynomial time algorithm for solving an NP-complete problem is made, that means all NP-complete problems are solvable in polynomial time&...
1 vote
177 views

### What is the definition of the Entscheidungsproblem (Decision Problem)?

I have been trying to find the most “formal” definition of the Entscheidungsproblem for the past couple of days now. On Wikipedia it states this: The problem asks for an algorithm that considers, ...
98 views

### Understanding the basics of the conjugacy problem better

There are classes of group presentations for which the conjugacy problem is known to be soluble, for example braid groups. Is the word “soluble” here a synonym for “decidable”? Of the groups in the ...
Let $M_1, \ldots, M_K$ be positive definite real symmetric matrices of dimension $n$. Let $R$ be an $m \times n$ matrix with $m < n$. Assume $R$ has full row rank. Fix $d\in\mathbb{R}^m$. Consider ...