# Questions tagged [decision-problem]

A question in some formal system with a yes-or-no answer.

64 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2k views

70 views

### turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
631 views

### Showing that $H'$ is not semi-decidable

I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have ...
81 views

### Efficiently decidable logics

So propositional logic (PL) is efficiently (in P) decidable because I can convert formulas to an equisatisifiable CNF-formula, negate and convert (efficiently, by De Morgans laws) to DNF. I can then ...
66 views

### Relevant subtree and relevant leaf in Machine Learning Decision Trees

I'm currently studying Decision Trees and the definition of a decision tree in our course is somewhat obscure for me. Nowhere in other online definitions of decision trees do I find something about ...
361 views

### Does FNP-complete = NP-complete?

I can't seem to find this stated explicitly anywhere, which makes me wonder if I have it all wrong. So first, let's say we view problems in NP as degenerate problems in FNP, where the codomain of the ...
86 views

### Deciding whether a CFG is parity absent

Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ ...
19 views

### Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?
I am supposed to find an algorithm solving the following problem: Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$. ...