Questions tagged [decision-problems]
A decision problem is a question (in some formal system) whose answer is either "yes" or "no".
116
questions
0
votes
0
answers
20
views
Proposed analysis techniques - optimal decision given expectation
I am going to conduct an analysis in order to "weight" different possibilities of actions in a given market. I have an overall level of effort that can be distributed accross the different ...
- 11
1
vote
0
answers
57
views
Is the three dimensions Navier-Stokes equations problem a P problem?
Edited. If we define this problem by a yes/no question, like:
« Does the 3D Navier-Stokes equations problem have a positive solution (which means that there are respecting problem conditions solutions ...
- 63
1
vote
0
answers
14
views
Proving undecidability of a problem by showing that a single instance is undecidable
In our theoretical computer science class, we are currently working with undecidable problems on Compositional Message Sequence Graphs (CMSGs). We proved in the lecture, that the existence of a safe ...
- 111
0
votes
0
answers
31
views
Unbiased decision rule.
The question is Problem 12 (p97, pdf p97) in Section 1.7 in Mathematical Statistics: Basic Ideas and Selected Topics. It can be calculated that
$$
\begin{aligned}
& E_{\theta} l (\...
- 397
2
votes
0
answers
54
views
Which branch of math theory could solve the task?
Imagine that we have a value $s_i = f(s_{i-1}, x_{i-1})$, reccurent formula $s_i$ with parameter $x_i$. $x_i$ values depends on $x_0$ and each $x_i$ is calculated in a diffenrent way. I guess it is ...
- 121
3
votes
1
answer
41
views
Decision procedure for whether the power series of a rational function has only nonnegative coefficients
My question is about rational functions of the form $f(x) = \frac{p(x)}{q(x)}$ where $p(x) = \sum_{i=0}^n p_i x^i$ and $q(x) = \sum_{i=0}^n q_i x^i$ with $p_i, q_i \in \mathbb{Q}$ and $q_0 \ne 0$. ...
- 138
0
votes
0
answers
41
views
Reduction from Traveling Salesman Problem
Consider the decision problem:
"Given a complete weighted graph $G=(V,E)$, an integer $k\in\mathbb N$ and two nodes $s,t\in V$ decide if $G$ has a path of at least weight $k$"
I had to ...
- 101
0
votes
0
answers
47
views
How can I reduce 3-SAT NAE to Set Partition?
I need to reduce Partition of a Set from 3-SAT NAE to prove that set partitioning is NP-Complete.
I have this:
Given an instance of NAE-3-SAT, the reduction builds an instance of the set partition ...
0
votes
0
answers
18
views
MCDA, Fuzzy analytic hierarchy process(FAHP), how to integrate user input data based on criteria into AHP calculation
i am developing a website that gives the best recommendation of school for all student using Fuzzy AHP(analytic hierarchy process). and i have a problem on how to integrate student data into my AHP ...
- 1
0
votes
0
answers
36
views
What condition on Decision space imply it's a decision tree
Let's say we have tabular data(numerical) and each column is dimension hence each row is a data point in $R^n$ if there are $n$ columns. The decision tree can be seen as the partition of the data now ...
- 1,025
1
vote
1
answer
136
views
How to determine whether a given convex polytope is contained in another given convex polytope?
Given a tall matrix $A \in \mathbb{R}^{m \times n}$ (where $m > n$) and a vector $b\in\mathbb{R}^{m}$, we say that they define the set $$\mathcal{S} = \left\{x\in\mathbb{R}^n: Ax\le b\right\}$$ ...
- 2,264
3
votes
0
answers
46
views
Minimum spanning forest, for a complete graph.
Given a complete Graph $G(V,E)$ with $|V|=kn$ and weights $w:E→N$ that satisfies "Triangular Inequality". That is, for any $v_1, v_2, v_3 \in V$,$$w(v_1,v_2)\le w(v_1,v_3)+w(v_3,v_2).$$
Can ...
- 71
4
votes
1
answer
69
views
Minimum spanning forest, where each tree has the same number of vertices.
Given a connected Graph $G(V,E)$ with weights $w\colon E\to\mathbb{N}$ and $|V|=kn$. How can I find the minimum spanning forest $T_1,T_2, \dots, T_n$ where each tree $T_i$ has exactly $k$ vertices?
I ...
- 71
0
votes
0
answers
54
views
How to proof that the union of two semi decidable languages ist semi decidable.
I am currently studying for my exam in theoretical CS.
In my lecture notes it says:
L1 ∪ L2 is semi decidable if L1 and L2 are semi decidable languages.
I want to ...
4
votes
1
answer
115
views
Presentation of a subgroup of a given index
I am unable to find an explanation of why it is possible to compute a finite presentation of a finite index subgroup in a given finitely presented group. More particularly, if $G$ is a virtually ...
- 309
0
votes
1
answer
70
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,403
2
votes
0
answers
33
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 ...
- 71
1
vote
1
answer
672
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$ ...
- 289
2
votes
1
answer
659
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
120
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 ...
- 33
1
vote
0
answers
29
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 $...
- 121
0
votes
0
answers
34
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
1
answer
88
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
54
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
119
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
15
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
259
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
56
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 ...
- 5,739
0
votes
0
answers
31
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 ...
- 524
2
votes
0
answers
262
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,890
1
vote
1
answer
61
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
69
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,382
0
votes
0
answers
42
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 ...
- 23
0
votes
1
answer
131
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
266
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
74
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
31
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 ...
- 113
0
votes
1
answer
65
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
67
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
106
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
129
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,900
0
votes
0
answers
30
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
111
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 ...
2
votes
1
answer
287
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 ...
- 23
0
votes
0
answers
46
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 ...
- 23
1
vote
0
answers
214
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 ...
- 361
2
votes
1
answer
69
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,721
0
votes
1
answer
163
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
663
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
157
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 ...
