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
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 ...
Mathman's user avatar
  • 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 ...
someone's user avatar
  • 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 ...
EricHier's user avatar
  • 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 (\...
香结丁's user avatar
  • 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 ...
Данила Алексеев's user avatar
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$. ...
Fabian Z's user avatar
  • 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 ...
Green's user avatar
  • 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 ...
Rodkaiser's user avatar
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 ...
Baeby's user avatar
  • 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 ...
GGT's user avatar
  • 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\}$$ ...
Arastas's user avatar
  • 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 ...
diego.0412's user avatar
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 ...
diego.0412's user avatar
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 ...
Heisenbug 's user avatar
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 ...
J.L.'s user avatar
  • 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 $...
Lázaro Albuquerque's user avatar
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 ...
Xiaoxiao's user avatar
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$ ...
linker's user avatar
  • 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},\...
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
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 $...
ygh's user avatar
  • 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 - \...
Uyen Pham's user avatar
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-...
Arone's user avatar
  • 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: ...
David Carral's user avatar
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 ...
Jossa's user avatar
  • 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}$...
OFM's user avatar
  • 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 ...
F.Hazi's user avatar
  • 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 ...
Trevor's user avatar
  • 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 ...
matty_k_walrus's user avatar
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.$ ...
Lee's user avatar
  • 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/...
groups123's user avatar
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_{...
mkultra's user avatar
  • 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 ...
zhukui bai's user avatar
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, ...
Ernie Vigelan's user avatar
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 ...
Slowflake's user avatar
-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 ...
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
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 ...
John M. Riveros's user avatar
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 ...
O'ara's user avatar
  • 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 ...
itsfarseen's user avatar
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 ...
Ski Mask's user avatar
  • 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 ...
xyz's user avatar
  • 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 ...
Alberto Tiraboschi's user avatar
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 ...
borroot's user avatar
  • 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 ...
borroot's user avatar
  • 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 ...
Luna's user avatar
  • 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 &...
boaz's user avatar
  • 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 ...
Kodora's user avatar
  • 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 ...
Kodora's user avatar
  • 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 ...
Luis Rodriguez Fuentes's user avatar