Questions tagged [decision-problems]
A decision problem is a question (in some formal system) whose answer is either "yes" or "no".
119
questions
1
vote
1
answer
37
views
Optimal ordering of a collection of gambles
An item is to be obtained at the minimum possible expected price. It can be obtained by paying a fixed price $F$, or by buying some gambles $G_i=(P_i,q_i)$ from a collection of offers $O=\{G_i|i\in\{0....
0
votes
0
answers
14
views
How to find a linear decision boundary of a linearly separable problem with unlimited class evaluations?
I have a binary classification problem, where my goal is to find a linear decision boundary (which I assume exists). The context of the problem is that I have an iterative optimization process, where ...
0
votes
0
answers
14
views
Calculation of normalized values for cost-type criteria in the weighted sum model
According to pymcdm WSM is calculated as follows:
$$ A_i^{\text{score}} =\sum_{j=1}^n \bar{x}_{i j} w_j \quad \text{for } i=1,2,3,\ldots ,m$$
Where:
$m$ is the number of alternatives
$n$ is the ...
2
votes
0
answers
63
views
Efficient proof that a number is NOT a Zumkeller number?
The subset sum problem is known to be NP-complete , so in general there is no efficient method to decide it , in particular to prove a negative result.
This problem arises in the problem to decide ...
0
votes
0
answers
18
views
Guess the number in the box - which complexity class does this belong in?
I'm trying to improve my understanding of complexity classes by reading the complexity zoo here, https://complexityzoo.net/Complexity_Zoo, and a number of other resources. I'm having an argument with ...
3
votes
0
answers
72
views
Can This Classical-Kleene Combination for Intuitionistic Fragment $\{ \neg, \vee, \wedge \}$ Be Extended to Include $\rightarrow$?
Over a year ago, I worked out a classical-Kleene combination logic that worked to preserve intuitionistic tautologies over the intuitionistic fragment with operators $\{ \neg, \vee, \wedge \}$, which ...
0
votes
0
answers
21
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 ...
1
vote
0
answers
60
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 ...
1
vote
0
answers
16
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 ...
0
votes
0
answers
49
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 (\...
2
votes
0
answers
55
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 ...
3
votes
1
answer
49
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$. ...
0
votes
0
answers
41
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
vote
1
answer
157
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\}$$ ...
4
votes
0
answers
54
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 ...