Questions tagged [decision-problems]
A decision problem is a question (in some formal system) whose answer is either "yes" or "no".
76
questions
1
vote
1answer
50 views
What does $w' := <M'>$ mean in the context of the Halting Problem?
I am studying the Halting Problem and I came across the following notation. I am not sure what it means. The context is as follows:
To prove that the Halting Problem is undecidable, we employ proof ...
0
votes
0answers
26 views
NP-Complete polynomial/linear transformations
I have been revising standard reductions for the following NP-complete problems:
SAT to 3SAT
3SAT to VERTEX COVER
VERTEX COVER to INDEPENDENT SET
INDEPENDENT to SET CLIQUE.
I understand that since ...
0
votes
0answers
19 views
Decision based on decision tree
Based on a text I created a decision tree. This decision tree shows options A, B and C. I calculated the value that could be expected for each decision and the highest one would be that of option C ...
0
votes
1answer
61 views
Is it true that every closed formula is decidable? Why?
I was wondering if every closed formula is decidable (in a complete system). Clearly a non closed formula is not decidable, since it can take some values for which it is true, and other for which it ...
1
vote
1answer
33 views
NP-completeness of undirected planar graph problem
I want to know whether a certain graph problem is NP-complete or not. The problem is as follows.
Given an undirected planar graph with in every vertex a number. Can you give every edge a direction ...
0
votes
0answers
19 views
NP-completeness of bipartite planar graph problem
I want to know whether a certain graph problem is NP-complete or not. The problem is as follows.
Given an undirected planar bipartite graph with in every vertex a number. Can you make a subgraph for ...
1
vote
0answers
45 views
Best algorithm for convex hull membership problem
Given a point $p \in \Bbb R^d$ and a finite set $S \subset \Bbb R^d$, I would like to determine if $p$ lies in the convex hull of $S$.
A literature search informed me that there are a lot of different ...
2
votes
1answer
49 views
Given matrix $A$, decide the existence of a $k \times k$ matrix $X$ such that $X^n=A$
Let $R$ be a commutative ring with an identity element $1$. Is there a $k\times k$ matrix $X$ over $R$ such that
$$
X^n=
\overbrace{
\begin{pmatrix}
1 & 1 & 0 & \cdots & 0\\
-1 &...
0
votes
0answers
18 views
Maximizing the probability of choosing a green ball from two boxes with decision theory
I have this excercise from a book of bayesian Analysis
Consider two boxes A and B each of which contains both red balls and green balls. It is known that, in one of the boxes, $\frac{1}{2}$ of the ...
1
vote
1answer
39 views
Best approach for Undecidability proof
Context:
Hi, my professor sent me this challenge and I got stuck. I thought using Rice's Theorem for this question, since $M$ is non-trivial, but he told me to use a reduction.
Is he right? Should I ...
0
votes
2answers
96 views
How to prove undecidability other than Rice Theorem?
Im studying Rice Theorem and I would like to verify its consistency. If I am able to prove de undecidability in other ways, the Rice Theorem would prove to be useful after all.
Im trying to find out ...
2
votes
1answer
68 views
Maximizing the probability of choosing a green ball from two boxes
I have this excercise from a book of bayesian Analysis
Consider two boxes A and B each of which contains both red balls and green balls. It is known that, in one of the boxes, $\frac{1}{2}$ of the ...
3
votes
0answers
51 views
Subset sum problem for geometric sequences
Problem Statement
Update: This problem has an update. See Edits section at the end.
Given a finite set $A \subset Z$, the Subset Sum Problem is a decision problem that answers the question Does any ...
0
votes
0answers
16 views
Shewhart charts change-point detection. Is there more simple way?
I am studying change-point detection algorithms using this book. The problem I am staring at is on the pages 27 - 28. The simplest algorithm explained here is the Shewhart Control Charts. The defines ...
1
vote
0answers
67 views
Probability - Decision Problem - Need help Modeling, intuition
This is a homework problem and I am not asking for a solution. Rather, I've been stuck for many hours and the professor has been no help. So
Consider the decision problem of whether a given positive ...
0
votes
1answer
28 views
Change point detection
I am studying this book. I want to learn change detection algorithms. There is the first approach called "Limit Checking Detectors and Shewhart ControlCharts" on the page 26. On the page 28 ...
0
votes
3answers
27 views
Determining if a vector belongs in the linear span
Fix a $\in$ $\mathbb{R}$. Consider the vectors $a + x + x^2$, $1 + x^2$ and $x$ in the $\mathbb{R}$-vector space $P(\mathbb{R})$ of polynomial functions over $\mathbb{R}$. Then $x^2$ belongs to the ...
2
votes
0answers
33 views
Check if a matrix has support
From Sinkhorn & Knopp (1967):
If $\mathbf{A}$ is an $N \times N$ matrix and $\sigma$ is a permutation of $\{1, \dots, N\}$, then the sequence of elements $a_{1, \sigma(1)}, \dots, a_{N, \sigma(N)}...
0
votes
1answer
39 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 ...
0
votes
0answers
38 views
Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP
Edit: An answer is available here: https://cs.stackexchange.com/questions/128388/nondeterministic-polynomial-time-algorithm-versus-certificate-verifier-for-showi/128391?noredirect=1#...
0
votes
0answers
9 views
Value iteration and utility function
my question is about the value iteration. What does it mean if the utility function V is negative?
For example one optimal policy yields the optimal V function: V*=(-0.5,0.6,0.6) and say chosing ...
0
votes
1answer
22 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
1answer
83 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
1answer
89 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, ...
2
votes
0answers
67 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 ...
0
votes
0answers
19 views
Is there a meaningful additive risk measure
An important property of coherent risk measures is subadditivity. But are there any additive risk measures that can be used in a meaningful way? (I would exclude the expectation for example)
0
votes
1answer
57 views
Why doesn't the incompleteness theorem answer the decision problem?
The answer (or impossibility of an answer) to Hilbert's Entscheidungsproblem or decision problem is generally attributed to Alan Turing and also independently to Church. My question is why Gödel's ...
0
votes
1answer
15 views
How to determine the existence of a solution to a system of homogenous quadratic inequalities and linear equalities?
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 ...
0
votes
2answers
40 views
Inclusion of polytopes
Let $C_{1}$ and $C_{2}$ be polytopes in $\mathbb{R}^{n}$ such that
$C_{1}=conv\left( V\right) $ with $V$ being a set of vertices. If
$V\subseteq C_{2}$, my question is $C_{1}\subseteq C_{2}$?
2
votes
1answer
58 views
How can the following lemma be used to solve the conjugacy problem for hyperbolic groups?
We are given the following lemma:
Let $G = \langle X \ | \ R\rangle $ be a $\delta$-hyperbolic group, then let $u,v \in X^\ast$ be two words such no shorter words in $X^\ast$ define the same elements,...
0
votes
0answers
57 views
Maximizing the probability of choosing a ball from two boxes
I am new here but I have a question that I would like to ask. If any body is in the know, kindly assist. The problem is from Berger (1985) statistical decision theory and Bayesian Analysis Exercise No....
2
votes
2answers
67 views
Algorithm to find equivalent nodes in isomorphic graphs
Suppose you are given two graphs with $v$ vertices and wish to check whether they are isomorphic are not. One possible way to do this is to enumerate all possible permutations of the $v$ vertices and ...
0
votes
1answer
30 views
Set inclusion between convex polytopes with $\mathcal{H}$-representation
Let $\mathcal{P}_1$ and $\mathcal{P}_2$ be two convex polytopes with $\mathcal{H}$-representation, i.e.,
\begin{align}
\mathcal{P}_1 &= \{x \in \mathbb{R}^n\colon A_1x \leq b_1\},\\
\mathcal{P}_2 ...
1
vote
0answers
34 views
Solutions to system using Fourier-Motzkin Elimination
I am trying to find a solution to this system using Fourier-Motzkin Elimination, but I don't know how to finish this. Here is what I have so far.
$x_1-x_2\leq 0,\quad x_1-x_3\leq 0,\quad -2x_1+2x_2+...
2
votes
1answer
54 views
Decision problem: Existence of a perfect number m larger than a natural number n
I am currently having a look at the slides from my theoretical computer science lecture and I am having trouble to understand a claim made. According to the slides the language
$L = \{ n \in \mathbb{...
3
votes
1answer
79 views
Decidability of halting problem for special kind of automata
Given an automaton $\mathcal{A} = \left\langle S, s_0, \delta \right\rangle$ over the finite alphabet $\Sigma$, where
$S$ is a finite set of states,
$s_0 \in S$ is an initial state,
$\delta\colon S \...
2
votes
1answer
120 views
When does a given system of linear inequalities form a bounded convex polytope?
We know that a Closed Convex Polytope may be regarded as the set of solutions to the system of linear inequalities:
$$\begin{array}{ccc}{a_{11} x_{1} +a_{12} x_{2}+\cdots+a_{1 n} x_{n}}\leq b_{1} \\ {...
2
votes
0answers
79 views
$\Sigma^1_1$-complete set of natural numbers of non-logical nature
I am interested in $\Sigma^1_1$-complete reals (i.e., subsets of $\omega$) of non-logical nature. I am more familiar with $\Sigma^1_1$-complete sets of reals that arise in computable structure theory, ...
0
votes
0answers
30 views
Any NP-Hard problem is reducible to other NP-Hard
I have the following problem:
$P$ is NP-hard, if and only if, there exists a NP-hard problem $Q$ such that $Q \preceq P$, i.e, $P$ is reducible to $Q$.
My attempt:
Let's show that $P$ is NP-hard. ...
0
votes
0answers
88 views
Does $A x > b$ have a solution?
Formulate a linear program that will determine whether or not $Ax>b$ has a solution, where $A$ is an $m \times n$ matrix and $b$ is an $m$-vector.
We were told to use Farkas Lemma, but are not ...
1
vote
1answer
34 views
Question regarding the formal definition of NP
I am reading the wikipedia article on the definition of NP. The verifier based definition of the complexity class NP is given by:
Alternatively, NP can be defined using deterministic Turing ...
2
votes
0answers
38 views
Specific edge-matching puzzle NP-complete
I'm a math student dealing with complexity theory for the first time.
I'm struggling with the following exercise, hope someone will help me!
I need to show that the following decision problem is NP-...
1
vote
1answer
33 views
there are decision problems that are computable and are not in P
I got this doubt, it is clear that there are non-computable problems that are not in P, for example Busy Beaver, but is this another true?
3
votes
1answer
164 views
Determining if a Vector is a member of a Convex Hull
Edit: Here is how the following sets are created:
$S$ is the set of all $n$-dimensional, multilinear trinomials that are strictly greater than $0$ on the interval $[0,1]^n$. $T$ are all miltilinear ...
2
votes
0answers
27 views
Markov decision process structural properties
I am trying to prove a structural property of a Markov Decision Process (MDP), but I have not been able to do so. I am wondering if someone can give me some insight in how to prove it or give me some ...
0
votes
1answer
47 views
When are two unlabelled simple graphs considered equal?
When are two unlabelled simple (not necessarily connected) graphs considered equal? I don't really find a way to formally state this.
Additionally, what might be a way to find the number of ...
3
votes
1answer
43 views
does checking if a matrix can have at least one positive number at each row by negation of columns a NP-complete problem?
Given a NxN matrix of numbers {-1, 0, 1} we want to check if it's possible to reach a state where each row contains at least one one only by changing the sign of columns (1 = -1, -1 = 1).
Is this a ...
2
votes
1answer
53 views
How to algorithmically decide if a given polytope is open?
Given a polytope $$P = \{{ \bf x} \in \mathbb{R}^n\mid{\bf A} {\bf x} \leq {\bf c}, {\bf A}\in\mathbb{R}^{m\times n},{\bf c}\in\mathbb{R}^m\}$$ find a fast algorithm that determines if $P$ is ...
5
votes
2answers
107 views
Does decidability imply inconsistency?
I have always thought that according to Gödel's incompleteness problems, every inconsistent theory would be decidable.
This is indicated, here for example: https://en.wikipedia.org/wiki/Decidability_(...
1
vote
1answer
76 views
Determining whether a polyhedral cone is a subset of another polyhedral cone
Let $A, B \in \mathbb{R}^{n \times n}$. The polyhedral cones of $A$ and $B$ are given by $$\mathcal{C}_A = \{ x \in \mathbb{R}^n : x = A \lambda, \mbox{ where } \lambda_i \ge 0 \mbox{ for all } i = 1, ...
