# Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

384 questions
Filter by
Sorted by
Tagged with
32 views

### Show that this language is undecidable

Given the language $K$ $=\{<M>$ where $M$ is a turing machine ( that is on the alphabet {0,1}) and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$ I would like to know if ...
55 views

### How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable?

So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.) Question 1 : Show ...
42 views

### any one can prove following inequality?

are for every $\alpha \in N$ , $\frac{1}{\alpha-2} \geq \frac{1}{\alpha}+\frac{1}{\alpha-1}$?
36 views

### Height of AVL tree with balance condition of 2

The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed ...
23 views

### Question about graphs and Eulerian path

An almost complete graph of n vertices is obtained from the removal of two edges of the complete graph of n vertices. For which values of n are there almost complete graphs that admit Eulerian paths? ...
14 views

41 views

### For an NFA, can we always find a RAM?

For an NFA, can we always find a RAM, which recognises the same language?
15 views

19 views

### Enumerating every “partnering” without repeating partners

I'm taking a class. In this class every week we have a partner. There are an even number of people in the class. We'd like avoid having repeat partners if possible so that everyone gets to work with ...
46 views

67 views

### Turing reducibility of 2 versions of the satisfiability problem

I need help with this problem. There are 2 versions of the satisfiability problem:  decision version: determine whether an arbitrary formula f is satisfiable or not  search ...
64 views

### Reducibility of 2 boolean satisfiability problems

I beg some help with this problem. There are 2 boolean satisfiability problems. Problem $A$: Determining whether an arbitrary formula of size $n$ is $satisfiable$. Problem $B$: Determining ...
37 views

Let TOT be the set of all Turing Machines that halt on all inputs. Find a computable set B of ordered triples such that: TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B] This definition means ...
34 views

### Is there a way to hash a turing machine?

If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which ...
178 views

### Recursive Algorithm to compute Square numbers

I figured out an algorithm to compute the square of a number (power of 2) in a recursive way backwards or forward. I don't think I have ever seen this anywhere else before, so I am curious if this ...
23 views

### Stable matching with dynamic preference lists

I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
101 views

### Prove or Disprove, 3SAT ≤p 2SAT, then P = NP

I know that 3SAT is in NP and 2SAT is in P. And 2SAT can reduce to 3SAT just says 3SAT is strictly harder than 2SAT, so I don't think this proves P = NP, but it doesn't seem to disprove it either.
40 views

### If a problem A ≤p B, then that B ≤p A, prove or disprove

I think the intuition is to disprove this by counter example, but what are 2 specific well known problems I can use as counter example?
### How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$? [closed]
I need help how to interpret the following notation for $f$: Zeroes and ones form a binary number which can be converted to decimal notation. Thus, we may think of the computer as calculating a ...