Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
529 questions
4
votes
1
answer
61
views
Complexity record for solving univariate quadratic equation over finite field
Given a finite field of order $2^{\lambda}$ (where $\lambda$ isn't integral), what's the time complexity of finding any solution of the equation $ax^2+bx+c=0$ in the said finite field?
The best ...
- 448
0
votes
1
answer
88
views
Cardinality of an Equivalence Relation on Finite and Infinite Sets
I was wondering about something. For a finite set $A$ with an equivalence relation $R$, I know we can find the cardinality of $R$ using the formula
$$
|R| = \sum_{i=1}^{k} |C_i|^2
$$
where $C_1, C_2, \...
- 91
0
votes
0
answers
87
views
Why is the Adleman’s index calculus complexity constant relative to the size modulus's size?
According to https://pages.cs.wisc.edu/~cs812-1/adleman.pdf the complexity is stated to be $e^\sqrt{log_eq×log_elog_eq}$, but since the algorithm operates in a similar fashion than the Pohlig Hellman (...
- 59
5
votes
0
answers
90
views
Is there a sub-quadratic algorithm to evaluate $\Pi_i\Pi_j\Pi_k\Pi_l(1+a_ib_jc_kd_l)$
I'd like to efficiently evaluate $\Pi_i^N\Pi_j^N\Pi_k^N\Pi_l^N(1 + a_ib_jc_kd_l)$ without enumerating the $N^4$ terms by brute force.
I was able to achieve a mildly-efficient $O(N^2log^2(N^2))$ ...
1
vote
1
answer
104
views
Help understanding how to reduce to a symmetry-based coloring problem (NP-completeness)
I'm working on a theoretical computer science problem and I'm honestly not sure how to approach it — so I’m hoping for some conceptual guidance.
The problem is to show that a specific coloring problem ...
- 11
3
votes
0
answers
127
views
Trilinear sum of characters in $\mathbb{Z}_2^n$
This is my first time asking a question on this site, as I believe my question is probably related to computer science (and possibly to the analysis of Boolean functions), and someone here might be ...
- 131
0
votes
1
answer
85
views
Prove for every graph G that if every vertex v∈V has deg(v)≥((n+1)/2)+1 then G is 2-connected
I had a question if this is possible to prove:
Prove for every graph G=(V,E), that if every vertex v∈V has deg(v)≥((n+1)/2) then G is 2-connected.
i tried by using the theorem that if every vertex has ...
- 1
-3
votes
1
answer
121
views
What is the difference between "inclusive and" and "exclusive and"
As we know that there is a difference between "inclusive or" and "exclusive or" same way can we explain the difference between "inclusive and" and "exclusive and&...
1
vote
1
answer
107
views
What's the real life uses of Reflexive Closure in computer science?
I was tasked to discuss Reflexive Closure, in relation to computer science. In Discrete Mathematics context, its basically a set that relates to an element itself. But I just can't find any ...
0
votes
1
answer
58
views
How did the author derive a string from a specific grammar?
Working on:
Richard Johnsonbaugh. (2018). Discrete Mathematics, 8/e (p. 608)
Given this grammar:
2. $T = \{a, b\}, N = \{\sigma, A, B\}$, with productions
$$
\begin{aligned}
\sigma &\to A, &...
- 139
3
votes
1
answer
180
views
Prime Factorization of a number implemented as a ternary search tree datastructure
Best to start with an example:
$$
826686=2 * 3^{10} * 7
$$
So by writing the nth prime as $p_n$ where n is called the index of the prime. (e.g. $23=p_9$ because it is the 9th prime occuring) we have ...
- 33
0
votes
1
answer
87
views
Finding the output string corresponding to an input string for a finite-state machine
Working on:
Richard Johnsonbaugh. (2018). Discrete Mathematics, 8/e (p. 590)
I am studying finite-state machines, and I have the following definition in my book:
Definition 12.1.8
Let $M = (I, O, S,...
- 139
0
votes
2
answers
128
views
How to interpret "implication holds" or "implication doesn't hold"?
Lets say we have a sentence, "If it is raining, then I will take the cab".
Let's say
$$
p: \text{It is raining} \\
q: \text{I will take the cab}
$$
In this if it is actually raining (...
- 208
0
votes
0
answers
145
views
Turing machine that makes exactly $2^{|x|}$ steps on any input $x$
I have the following problem:
Construct a Turing-machine that makes exactly $2^{|x|}$ steps on any input $x$. The machine can have $k$ tapes but only a fixed number of states (thus, the number of ...
- 119
1
vote
2
answers
586
views
The number of triple intersections of lines
Suppose we have $n$ lines in plane which is divided equally among the three sets(the lines in each set are equally spaced), each of contains $n/3$ lines. And they intersect each other and creates a ...
user150715