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
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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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},\...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 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 - \...
user avatar
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)$, ...
user avatar
  • 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-...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
  • 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}$...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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.$ ...
user avatar
  • 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/...
user avatar
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_{...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 &...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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)}...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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&...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 452