# Questions tagged [decision-problems]

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

116 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
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 ...
1 vote
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 ...
31 views

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 ...
1 vote
29 views

1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 &...
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 ...
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 ...