Skip to main content

Questions tagged [decision-problems]

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

Filter by
Sorted by
Tagged with
-2 votes
0 answers
44 views

Relevance of $P(A \cup B)$

Probability means the chance of occurring a specific event. My question : how necessary is $P(A\cup B)$ because it will not pinpoint the particular event ? What conclusions do we make from $P(A\cup B)$...
ml ds's user avatar
  • 9
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....
MarioVX's user avatar
  • 191
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 ...
oskar0711's user avatar
0 votes
0 answers
13 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 ...
user32882's user avatar
  • 702
2 votes
0 answers
62 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 ...
Peter's user avatar
  • 85.1k
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 ...
3mar's user avatar
  • 1
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 ...
Joshua Harwood's user avatar
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 ...
Mathman's user avatar
  • 11
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 ...
someone's user avatar
  • 63
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 ...
EricHier's user avatar
  • 111
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 (\...
香结丁's user avatar
  • 419
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 ...
Данила Алексеев's user avatar
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$. ...
Fabian Z's user avatar
  • 138
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 ...
GGT's user avatar
  • 1,065
1 vote
1 answer
155 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\}$$ ...
Arastas's user avatar
  • 2,364
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 ...
diego.0412's user avatar
4 votes
1 answer
72 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 ...
diego.0412's user avatar
0 votes
0 answers
73 views

How to prove 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 ...
Heisenbug 's user avatar
4 votes
1 answer
135 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 ...
J.L.'s user avatar
  • 309
0 votes
1 answer
92 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 $...
Lázaro Albuquerque's user avatar
2 votes
0 answers
34 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 ...
Xiaoxiao's user avatar
1 vote
1 answer
943 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$ ...
linker's user avatar
  • 289
2 votes
1 answer
913 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},\...
Anonymous's user avatar
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 ...
Prboetic's user avatar
1 vote
0 answers
30 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 $...
ygh's user avatar
  • 121
0 votes
0 answers
36 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 - \...
Uyen Pham's user avatar
0 votes
1 answer
100 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-...
Arone's user avatar
  • 3
0 votes
1 answer
59 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: ...
David Carral's user avatar
0 votes
0 answers
135 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 ...
Jossa's user avatar
  • 1
1 vote
0 answers
16 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}$...
OFM's user avatar
  • 25
0 votes
0 answers
321 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 ...
F.Hazi's user avatar
  • 1
0 votes
2 answers
65 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 ...
Trevor's user avatar
  • 6,004
0 votes
0 answers
33 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 ...
matty_k_walrus's user avatar
2 votes
0 answers
302 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.$ ...
Lee's user avatar
  • 1,910
1 vote
1 answer
65 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/...
groups123's user avatar
0 votes
2 answers
74 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_{...
mkultra's user avatar
  • 1,382
0 votes
0 answers
46 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 ...
Yuhang Bai's user avatar
0 votes
1 answer
134 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, ...
Ernie Vigelan's user avatar
1 vote
2 answers
274 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 ...
Slowflake's user avatar
-1 votes
1 answer
81 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 ...
Johan's user avatar
  • 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 ...
Viren Sule's user avatar
0 votes
1 answer
74 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 ...
John M. Riveros's user avatar
0 votes
1 answer
81 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 ...
O'ara's user avatar
  • 23
2 votes
1 answer
115 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 ...
itsfarseen's user avatar
1 vote
1 answer
162 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 ...
Ski Mask's user avatar
  • 1,928
0 votes
0 answers
36 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 ...
xyz's user avatar
  • 43
0 votes
1 answer
127 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 ...
Alberto Tiraboschi's user avatar
2 votes
1 answer
307 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 ...
borroot's user avatar
  • 23
0 votes
0 answers
53 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 ...
borroot's user avatar
  • 23
1 vote
0 answers
245 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 ...
Luna's user avatar
  • 371