Skip to main content

Questions tagged [decision-problem]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
46 views

Non-deterministic TM with an oracle to $R$

Let $R$ be the set of all decidable languages. Consider $P^R$. That is, the set of all languages that can be decided via a polynomial time deterministic TM with an oracle to any language $L\in R$. I'd ...
Mařík Savenko's user avatar
3 votes
0 answers
48 views

Is the definition of "computational problem" on Wikipedia correct?

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...
pabloealvarez's user avatar
7 votes
1 answer
91 views

Is this "binary submatrix sum equation" problem NP-hard?

There is an unknown matrix $A$ of $R$ rows and $C$ columns. The entry at the $r$-th row, $c$-th column is $A_{rc}$. The matrix is a binary matrix, i.e. each entry is either 0 or 1. Another matrix $B$ ...
Bubbler's user avatar
  • 488
2 votes
1 answer
103 views

A paradox about cardinality of ALL and arithmetic hierarchies ― Did I just prove that ZFC is inconsistent?

This problem arose when I tried to find the arithmetic hierarchy that $\mathsf{ALL}$, the class of all formal languages over a finite alphabet, corresponds to (like how $\mathsf{R} = \Delta^0_1$ and $\...
Dannyu NDos's user avatar
2 votes
0 answers
31 views

Complexity of strong graph realization problem

Given a simple graph $G$, let $k^{th}$ degree of a vertex $v_i\in G$ denote the number of vertices that have distance $k$ from $v$. Notice that first degree is equivalent to degree by standard ...
rus9384's user avatar
  • 1,781
0 votes
1 answer
20 views

Concise definitions for different types of computational problems

It is very common to define a decision problem $L$ in the following way. Let $f \colon \Sigma^{*} \to \{0,1\}$. Then $L = \{x \in \Sigma^* \mid f(x) = 1\}$. Effectively, $L$ contains all instances $x \...
user319109's user avatar
2 votes
1 answer
41 views

Number of configurations, non-deterministic $LBA$ and $A_{LBA}$

The membership problem $A_{LBA}$ for a deterministic $LBA$ is decidable because the number of configurations that a $LBA$ can assume is finite. Since this number is also finite for a non-deterministic ...
Marcus's user avatar
  • 139
1 vote
1 answer
63 views

Graph Coloring Decision Problem Reduction to Prove NP-Complete

I am doing research into NP-Complete problems and more specifically started looking into the Graph Coloring Decision Problem or the k-Coloring problem, as described here: Given a graph $G = (V, E)$ ...
Darien's user avatar
  • 11
2 votes
1 answer
33 views

Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

If $G$ is a CFG, is it decidable whether $L(G)=\Sigma^+=\Sigma^*\setminus\{\epsilon\}$? I have no idea which in direction to go. I feel like it is undecidable, but can't seem to find any proof. I ...
PranksterSabeleye's user avatar
1 vote
1 answer
13 views

Special case of 2-dim subset sum problem with only 0 and 1s

I am currently researching about a statistical project, where a special computer science problem showed up. I am wondering about the following: Suppose I have many two dimensional vectors all of the ...
Bailey Hor's user avatar
-2 votes
1 answer
30 views

How do you show that Cosmic Kite Problem is NP complete?

A "cosmic kite" of size k consists of a clique of k nodes with a path of k nodes that unfolds from one of the nodes in the clique. Cosmic Kite as decision problem Input: a graph G = (V, E) ...
Nicolò Bonacorsi's user avatar
1 vote
1 answer
62 views

Does the Subset Product Problem remain NP-complete if repetition in S is not allowed?

Just curioius, I wanted to know when $S$ ={set of divisors of N} and we're given $N$ a target product. Our goal is to decide if a combination in $S$ has product equal to N. Does the problem remain NP-...
The T's user avatar
  • 321
2 votes
1 answer
94 views

Determining whether two special variants of knapsack have the same optimal value

Given two unbounded knapsack instances, $K_1 = (W_1, weights, values), K_2 = (W_2, weights, values)$, where $W_1 \ne W_2$, what is the complexity of determining $v(K_1) = v(K_2)$ where $v$ returns the ...
rossignol's user avatar
1 vote
1 answer
38 views

Decidability terms clarification

I just need some clarification regarding the different terms we use in theoretical computer science, especially regarding decidability. Decidable: A language $L$ (a set of strings) is decidable if ...
Just Curious's user avatar
0 votes
0 answers
31 views

What does a problem not in $NSPACE(cn / \log(n))$ tell me?

I have the following two resuts taken from the book "The Classical Decision Problem". How does Corollary 6.3.28 follow? How can I derive PSPACE-hardness from non-membership in $NSPACE(cn / \...
user1868607's user avatar
  • 2,194
1 vote
0 answers
24 views

Stable Flow Problem with one sided preferences

I'm currently working on a problem to come up with ideas to solve a stable flow problem but unlike the traditional stable flow problem where every node has preferences on its incoming and outgoing ...
Finn's user avatar
  • 11
1 vote
1 answer
117 views

Reduce CNF-SAT to decision problem

Given CNF-SAT reduce it to the following decision problem: Given n items, m groups (and for each group a set of items) and a ...
popcorn's user avatar
  • 183
0 votes
1 answer
13 views

Transform OTM for Problem π to DTM ∈ DSPACE(n)

Given an Oracle Turing machine ($OTM$) that solves Problem π in max. 2n space, so $O(n)$ space and $O(n^2)$ time. Is there a DTM that can solve $π$ in $O(n)$ space if time doesn't matter? (The length ...
Theorynoob's user avatar
5 votes
3 answers
1k views

Small doubt concerning cardinality of set of problems and algorithms?

I write this question because my professor in Algorithm Analysis briefly mentioned some property related to the countability/uncountability of the set of strings/problems/algorithms and the consequent ...
Sho's user avatar
  • 159
0 votes
0 answers
36 views

Greedy algorithm for trading cryptocurrencies with perfect price information

Assume the following hypothetic scenario: You know the values $v_1^0, \ldots, v_n^0$ of $n$ cryptocurrencies. You know the values this currencies will have for the following $m$ days; this is, $v_0^1,...
lafinur's user avatar
  • 195
1 vote
0 answers
31 views

Complexity class of a problem asking for a chance of receiving an item

I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a ...
rus9384's user avatar
  • 1,781
0 votes
0 answers
34 views

An Example of the Conjuction of Two NP-Complete Decision Problems Being Polynomial Time Solvable [duplicate]

Firstly, we define A and B as two decision problems with the same set of inputs. Define a new decision problem "A AND B" as follows: The input to "A AND B" is any valid input x for ...
Oluchi A's user avatar
0 votes
0 answers
156 views

Non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$

I was trying to figure out how can I construct a non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$ I looked at some of the proposed solutions here : Turing ...
Yarin's user avatar
  • 275
0 votes
0 answers
31 views

How to formulate "The general Sudoku problem is in P" formally and rigorously? How to calculate then the input size?

We consider a partially filled starting grid, where $n^2$ is the side size of the grid, $m$ is the number of non-empty initial squares, $f$ is the function that places randomly initially the integers ...
someone's user avatar
  • 11
0 votes
1 answer
30 views

Is « Does exist at least one function $u$ such that $f(u(0)) \ne g(u(0))$? » an NP problem? or a P problem?

$f$ and $g$ being known functions. We suppose that the problem is solvable. To me, for the moment, this question, if a decision problem it is or can be, is more an NP rather than a P problem, because ...
someone's user avatar
  • 11
2 votes
1 answer
62 views

Subset sum reducible to barter economy problem?

I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
redbull_nowings's user avatar
1 vote
1 answer
106 views

If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?

First, can the Navier-Stokes problem be a formal computable one? like a P problem? Then, how to define the corresponding language? Would it only be the set of equations, or something else? Then, could ...
someone's user avatar
  • 11
0 votes
0 answers
25 views

Greedy algorithm for minimising the number of encountered obstacles from multiple start points to single endpoint in a grid

I am given a $N$ x $M$ sized grid and $K$ start points $S = (s_1, s_2, .. s_k)$ where each $s_k = (x_k,y_k)$ representing the position on the grid. I am also given a single endpoint $(x_{end}, y_{end})...
calveeen's user avatar
  • 141
2 votes
0 answers
24 views

Stålmarck's method, can triplets be dropped once they triggered equivalences

In Sheeran, Mary, and Gunnar Stålmarck: A tutorial on Stålmarck’s proof procedure for propositional logic there is an example application of the method to...
user3128's user avatar
1 vote
1 answer
65 views

Do function problems have an interpretation in terms of formal languages?

In computational complexity theory, decision problems are typically defined as formal languages, and complexity classes are defined as the sets of the formal languages that can be parsed by machines ...
user avatar
19 votes
2 answers
4k views

Why are computability problems always written in full caps?

Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, ...
Rexon112's user avatar
  • 191
0 votes
1 answer
33 views

If I want to prove that a problem is in NP, can the vertifier use exponential space?

I want to prove that a problem is in NP. I have a witness (of polynomial size), and a verifier that runs in polynomial time. However, this verifier uses exponential space, becuase it has to generate ...
user606273's user avatar
0 votes
3 answers
118 views

Does exist an algorithm that decides whether a program halts or not as its timeout approaches to infinity?

By an algorithm $A(p, t)$ attempting to decide whether the program $p$ halts or not by running the program for $t$ seconds (the timeout) and trying to prove that it doesn't halt at the same time, can ...
sbh's user avatar
  • 53
-1 votes
1 answer
49 views

Schaefer's dichotomy theorem and limits on the formula length

Schaefer's dichotomy theorem ensures than when a constraint satisfiability problem satisfies certain conditions, the problem is either in $\mathsf P$ or is $\mathsf{NP}$-hard. Suppose the following ...
rus9384's user avatar
  • 1,781
2 votes
1 answer
123 views

On hardness of finding dominating sets in triangle-free regular graphs

A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices ...
Ankit Gayen's user avatar
-2 votes
2 answers
122 views

Can we tell if we can tell if an algorithm halts or not?

We proved that, there exist no algorithm so it can tell us if an algorithm halts or not (a.k.a. the halting problem is undecidable). But it surely can handle some of those; can we tell which of those ...
sbh's user avatar
  • 53
0 votes
1 answer
90 views

Max Unique Clique in $\Sigma^2_p$

I want to prove that the language $\text{Max-Unique-Clique} = \{<G> | \text{The maximal clique of $G$ is unique}\}$ is in $\Sigma_2^p$ by using the following $\Sigma_2^p$ machine: The machine ...
OriFrid's user avatar
  • 110
2 votes
1 answer
292 views

Constructing equivalent (to a polynomial-time degree) decision problems from function problems

Let's say we're some function problem, $R \subseteq \Sigma^* \times \Sigma^*$, where $\Sigma = \{0, 1\}$ and some oracle $O_R$ that solves $R$. Now, we're given some language, $L \subseteq \Sigma^*$ ...
Andrew Baker's user avatar
0 votes
1 answer
108 views

Minimal Hitting Sets Problem

Let $\mathcal{I} = \{I_0, \ldots, I_{m-1}\}$ a collection of subset of some universe $U$. We want to find a partition $P$ of $\mathcal{I}$ of minimal cardinality such that the intersection of each set ...
matteo_c's user avatar
  • 173
1 vote
1 answer
85 views

Decision version of optimization problems with polynomial-time approximation algorithms

Given an optimization problem $X$, it is easy to construct a decision problem $Y$, such that there is a two-directional polynomial-time reduction between $X$ and $Y$. Therefore, we can define a class ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
89 views

Why aren't promise problems just decision problems; can't we encode the promised inputs in the alphabet?

I don't really understand why promise problems are classified differently than decision problems. Consider this problem as an example. Given some real number between $0$ and $1$, determine if it ...
Loic Stoic's user avatar
0 votes
1 answer
142 views

Ackermann Decision Problem

I have been studying the Ackermann function, specifically the two-argument Ackermann–Péter version. With the Ackermann function, I developed a problem I call the "Ackermann Decision Problem" ...
CoalLad's user avatar
  • 143
1 vote
1 answer
86 views

Why is 3-co-SAT not in P?

The 3-co-SAT problem consists of deciding whether if a 3CNF formula, has an unsatisfiable assignment of variables, i.e., assignment of variables that evaluates to 0. We know that 3-co-SAT is in coNP, ...
Denizalp's user avatar
0 votes
1 answer
50 views

Is $\overline{A_{TM}}$ co-NP Hard?

I know that $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$ is NP-Hard: By showing a polynomial time reduction - $A \le_p A_{TM}$: Let $A \in NP$, then there exists a $NTM$ that decides $A$ in ...
Geo's user avatar
  • 47
1 vote
1 answer
76 views

Is the set of instances of PCP, which have a solution, semi-decidable?

My idea was that it is because we can construct a TM M' that simulates a TM M that is to find a solution for a PCP instance. M' accepts if M accepts, rejects if M rejects, and doesn't halt if M does ...
Natalia Markoborodova's user avatar
0 votes
1 answer
47 views

Integer factorization: Why can't we use the test algorhitm to create an algorhitm to decide the factoring decision problem in polynomial time?

I'm reading Nielsen and Chuang. On page 142 the integer factoring decision problem is introduced: The integer factorization problem can be reduced to a decision problem: Given a composite integer m ...
Opinel's user avatar
  • 11
1 vote
1 answer
63 views

The meaning of Tautology and Contradiction in Complexity theory

I recently had this question answered on stack exchange: if X is in NP but Y is not in NP then can X be reduced to Y? The answer proposed a counter example using an element of complexity theory I had ...
bmanicus131's user avatar
0 votes
1 answer
111 views

Show that $\text{BOOL-VAL}$ and $\text{DNF-SAT}$ is decidable in linear time

A boolean expression is valid if it is true for every valuation. The problem $\text{BOOL-VAL}$ asks whether a given boolean expression is valid. As the question suggests I need to show that $\text{...
user avatar
0 votes
1 answer
104 views

if X is in NP but Y is not in NP then can X be reduced to Y?

I have been led to believe that the following statement $X \in NP \land Y \not\in NP \implies X \not\le^m_p Y$ Is True. But I am having difficult proving it. And I'm not even sure it IS true anymore. ...
bmanicus131's user avatar
0 votes
2 answers
153 views

Is a language semi-decidable iff it is reducible to ATM?

Thank you. I see how it makes sense going in the opposite direction but i need help proving that this is true. Below is the definition of ATM. ATM={<M,w>| a TM, M accepts w} The question from my ...
Carrey's user avatar
  • 1

1
2 3 4 5
11