Questions tagged [decision-problems]
A decision problem is a question (in some formal system) whose answer is either "yes" or "no".
125 questions
0 votes
0 answers
27 views
Is this approach for positive predictive value (PPV) correct?
I am working with genetics data where an observation occurs at each nucleotide. The probability that an observation matches the reference nucleotide is assumed to follow a binomial probability ...
- 399
14 votes
2 answers
2k views
Does there exist a computer program that is able to determine whether a given function is uniformly continuous?
I was wondering if someone might know whether there exists (or whether it is even possible) for a computer program to process a given function and determine whether it is uniformly continuous. I have ...
- 481
2 votes
2 answers
198 views
What is the most efficient way to verify whether a given square matrix is a Hadamard matrix?
I am a network optimization engineer working on space-time block code diversity problems. In this field, Hadamard matrices serve as a fundamental building block for creating space-time diversity ...
1 vote
0 answers
79 views
PSPACE is closed under polytime reduction
A class $C$ is closed under polynomial time reductions if for every two languages $𝐿_1 , 𝐿_2$ such that $𝐿_1 \leq_{𝑝} 𝐿_2$ and $𝐿_2 \in C$, it holds that $𝐿_1 \in C$. My question is how to ...
- 131
0 votes
1 answer
76 views
Is TSP known to be co-NP?
The Travelling Salesman Problem is famously known to be NP. I was wondering if it is also known whether or not it is co-NP (i.e. its complement is NP)? If it is known a reference would be much ...
2 votes
1 answer
61 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....
- 311
5 votes
1 answer
251 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 ...
- 478
1 vote
0 answers
29 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 ...
- 111