Questions tagged [decision-problems]
A decision problem is a question (in some formal system) whose answer is either "yes" or "no".
100
questions
0
votes
1
answer
33
views
Reducing to an NP-complete problem
If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$?
I think we should be able to say that $R$ is in NP since an instance of $...
- 2,238
2
votes
0
answers
23
views
Is there an algorithm that can compute finite presentations for finitely presentable subgroups in a FP group with solvable word problem?
Given a group and its finite presentation $G=\langle A\mid R\rangle$, I want the following algorithm:
Input: a finite set $W$ of words in $A\cup A^{-1}$ that generates a finitely presentable subgroup ...
- 51
0
votes
0
answers
9
views
AO* algorithm to solve Canadian Traveller Problems: how are nodes expanded?
I'm re-implementing a AO* algorithm to solve Canadian Traveller Problems (CTPs), of which numerous variants exist like this one. In a nutshell, a CTP consists in reaching the goal vertex of a graph ...
- 145
1
vote
1
answer
146
views
Point in Polytope?
Context: This question is somewhat identical to this on MathOverflow, it’s different in that it only focuses on the formula of the solution to the underlying problem.
Suppose I have a convex hull $H$ ...
- 177
2
votes
1
answer
135
views
Intersection of convex hulls
I have two polyhedral sets $\mathscr{P}_1, \mathscr{P}_2,$ defined as convex hulls
$$\mathscr{P}_1 = \mbox{conv} \left\{ v_{1},\dots, v_{N} \right\}, \qquad \mathscr{P}_2 = \mbox{conv} \left\{ w_{1},\...
- 51
0
votes
1
answer
104
views
Checking if a matrix is zero deletable?
Given a matrix $\in [0,1]$. Delete operation is defined as: If one of the elements of the matrix contains 1 or 2 it can be deleted and replaced by 0.
A matrix is zero deletable if there is a chain of ...
- 3
1
vote
0
answers
25
views
How to determine if $x$ does not belong to $L \in NP$ in a finite number of steps
I'd prefer to stick to the "deterministic" definition of NP, i.e:
-A language $L\subseteq {0, 1}^*$ is in $NP$ if there exists a polynomial $p : N \rightarrow N$ and a polynomial-time $...
- 71
0
votes
0
answers
29
views
Find decision rule using Rao-Blackwell
Suppose that an observation $x \in (-1,1)$ comes from a sample model with a parameter $\theta$, with density function:
$$
f(x\mid\theta) = \begin{cases}
\theta\ if -1 < x < 0\\
1 - \...
- 11
0
votes
0
answers
126
views
Prove that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete
I want to prove that a subproblem of the known, $\mathcal {NP}$-Complete, Sparse Subgraph problem is $\mathcal {NP}$-Complete as well.
Sparse Subgraph problem:
Input: An undirected graph $G(V,E)$, ...
- 414
0
votes
1
answer
20
views
Prove that the preferences follow the Von Neumann and Morgensten's axioms
I'm studying Decision Theory from the book 'An introduction to decision theory' by Martin Peterson, and there is a problem that I don't understand how to solve. The problem is:
You prefer a fifty-...
- 3
0
votes
1
answer
39
views
Satisfiability of Second-Order Logic: Is this Decision Problem Complete for Some Level of the Arithmetical Hierarchy?
Consider the following decision problem defined in terms of input/output:
Input: a second order logic [1] theory $\mathcal{T}$ (i.e., $\mathcal{T}$ is a set of second order logic formulas)
Output: ...
0
votes
0
answers
96
views
I need to prove that this Harry Potter problem is NP-Hard. To what problem can it be compared for reduction?
Harry Potter is looking for a bowtruckle that is hiding in a graph and has made
itself invisible. Harry tries to find the bowtruckle by casting the spell rivilio trullio while aiming his
wand at a ...
- 1
1
vote
0
answers
14
views
NP-hardness via polynomial time reduction
I am trying to show a decision problem is NP-complete, using a polynomial-time reduction. As this is a homework question I won't post the exact question but the gist is this:
"Let $k\in\mathbb{N}$...
- 25
0
votes
0
answers
74
views
Multitape Turing Machine - Check input's primality
I've got this homework for next tomorrow and unfortunatelly I have no idea how to design this machine.
Requirement: Build a 2-tapes Turing Machine, which has a number as input a natural number (unary ...
- 1
0
votes
2
answers
42
views
Must every Turing-complete language be able to enumerate precisely those algorithms which return a particular value?
This kind of enumeration is particularly easy with some languages. For example, using SKI combinators, start with the expression $\mathbf{SKK}$ (Church encoding for $1$) and systematically apply the ...
- 4,941
0
votes
0
answers
29
views
How would you design an algorithm to solve this decision problem?
Suppose I want to design an algorithm that, for an arbitrary polynomial $p$, returns YES iff there are two roots $z_1$ and $z_2$ of $p$ such that $\left|z_1 - z_2\right| = 1$.
How do I design such an ...
- 514
2
votes
0
answers
102
views
How to check the feasibility of standard LMI using Matlab/CVX?
In the wikipedia page of LMI, the standard form is given by
$$A_0+y_1A_1+y_2A_2+\cdots+y_mA_m \succeq 0,$$
where $A_i$ are $m\times m$ symmetric matrices and $y_i$ are real vectors, $i=1,2,\ldots m.$
...
- 1,559
1
vote
1
answer
41
views
Conjugacy problem in hyperbolic groups: pigeonhole principle
I am trying to understand the proof of the conjugacy problem for hyperbolic groups: see
http://andreghenriques.com/Teaching/GeometricGroupTheory.pdf Lemma 6.2
https://www.math.ucdavis.edu/~kapovich/...
- 13
0
votes
2
answers
61
views
Does this system of inequalities have a solution?
Consider the following system of inequalities:
$$ \left\{ \begin{array}{ll}
x_{ab}+x_{ac}+x_{ad}+x_{abc}+x_{abd}+x_{acd}+x_{abcd}\ge 4+x_{bc} +x_{bd}+x_{cd}+x_{bcd}\\
x_{ab}+x_{bc}+x_{bd}+x_{abc}+x_{...
- 1,320
0
votes
0
answers
35
views
Are two optimization problems equivalent?
In complexity theory. There are two optimization problems. If decision problems associted with them are all NPC, then we know the two decision problem are equivalent. Are two optimization problems ...
- 11
0
votes
0
answers
11
views
How to convert a Query Evaluation Problem into a decision problem?
Let's define the Query Evaluation Problem (QEP) as:
Given a query q in L and a database instance D, evaluate q(D).
I wonder how to convert QEP into a decision problem. What's in my mind is that this ...
- 23
0
votes
1
answer
95
views
Is p-dimensional matching with $(p-1)n$ edges NP-hard? What about $3n$ edges? [closed]
Let $p\geq 3$ an integer. I am wondering whether or not the following problems are NP-hard or not (and if they are, I am looking for a convincing argument, or even better a detailed proof):
Let $V_1, ...
1
vote
2
answers
210
views
Is guessing person's name an NP problem example?
Say you want to guess someone's name. It is easy to check if their name is "Sarah" since you can ask them. However, if you are guessing from big enough set of names, you might spend eternity ...
- 27
-1
votes
1
answer
67
views
For which $a,b,c$ is the diophantine quadratic equation $ax^2+bx+c=y^2$ soluble?
Given $a,b,c\in\mathbb{Z}$, consider the quadratic equation $ax^2+bx+c=y^2$. Are there any general methods for deciding whether this equation has any integer solutions for $x,y$, given the ...
- 261
0
votes
0
answers
19
views
Complexity of representing all satisfying assignments
I am not formally educated in Complexity Theory hence asking this question. In which complexity class should the problem of representing all satisfying assignments of a Boolean system (equivalently a ...
- 103
0
votes
1
answer
31
views
Getting a first-order condition of Risk Adverse selection problem
I'm struggling to find out some basic maximization problem associated to the first order condition of a problem. The problem is an insurance example, where there's an strictly risk-adverse decision ...
0
votes
1
answer
57
views
How to check if $Ax<0$ has an answer?
Given matrix $A \in \Bbb R^{m \times n}$, where $m \ll n$, can I check whether $Ax<0$ has a solution $x \in \Bbb R^{n \times 1}$?
The operation $<$ is taken coordinate-wise. I am not sure but I ...
- 23
2
votes
1
answer
59
views
NP Hardness of odd degree subgraph problem
Problem: Given a graph G and a positive integer $k$, does there exist a $G' \subseteq G$ containing exactly $k$ edges, such that all vertices of $G'$ are of odd degree.
Is this problem NP-Hard or is ...
- 143
1
vote
1
answer
66
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 ...
- 1,850
0
votes
0
answers
23
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 ...
- 43
0
votes
1
answer
84
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
1
answer
120
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 ...
- 13
0
votes
0
answers
30
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 ...
- 13
1
vote
0
answers
104
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 ...
- 351
2
votes
1
answer
54
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 &...
- 4,316
0
votes
1
answer
58
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 ...
- 1
0
votes
2
answers
355
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 ...
- 1
2
votes
1
answer
95
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
0
answers
102
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 ...
- 1,075
1
vote
0
answers
82
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 ...
- 11
0
votes
1
answer
34
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
3
answers
39
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 ...
user773349
2
votes
0
answers
52
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)}...
- 195
0
votes
1
answer
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 ...
0
votes
1
answer
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 ...
- 3
1
vote
1
answer
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
1
answer
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, ...
- 49
2
votes
0
answers
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 ...
- 207
0
votes
1
answer
133
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 ...
- 77
0
votes
1
answer
37
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 ...
- 452