All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag.

learn more… | top users | synonyms

0
votes
1answer
12 views

Given a set S, find any N numbers than sum to X

Similar but different from the problem here: Find numbers in a set whose sum equals x I have an unsorted set S of real numbers, and need to sum elements from S to find the real number X; However, It ...
1
vote
0answers
26 views

Tools (electronic notebook and ontology viewer) of mathematical formulas (definitions and facts)

I am reading math books and articles (for applications in other disciplines, mostly about logics for computer science and AI) and the hardest part is to memorize formulas, to look up some ...
0
votes
1answer
30 views

Number of $n$-bit strings that contain from none to $n/2$ zeroes

This is a problem that revolves around symmetry. I recognize that if there is a 4-bit string that it will have 1110 as an answer, but it will also have 0111 as an answer. The thing is, I'm not sure ...
2
votes
1answer
42 views

Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
0
votes
2answers
27 views

Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
0
votes
0answers
18 views

turing machine accept and reject state

I am pretty new to Turing Machines and I am trying to understand the basic things first...so my question is , would this machine accept all words ending in 'a' ? if ...
0
votes
1answer
17 views

Strong one-way functions: a remark on the definition

Notation: $\Sigma^k$ is the set of $k$-strings on the alphabet $\Sigma$; $\Sigma^\ast$ is the set of all finite dimensional strings on the alphabet $\Sigma$. In the context of computer-science a ...
1
vote
1answer
32 views

Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
0
votes
0answers
18 views

Show L1 is in P, given that L2 is in P and L1 <=p L2

Given L1 and L2 are languages over alphabet Z. Also given that L1 <=p (polynomial time computable) L2 and L2 in P. What is the best way to show that L1 is in P (through definitions of class P and ...
1
vote
1answer
15 views

having hard time reading symbols in this Turing Machine

I am reading few books and I am looking at different examples of a Turing Machine, and I am getting frustrated reading symbols especially in this example...What does ...
0
votes
0answers
38 views

how do I make this post machine accept aab or baa?

so far I made it accept, a, aaa,bab but now I want strings aab or baa. How would I do this ? this is what I have so far... edit: @Hagen von Eitzen here is the example of Post Machine that a lot of ...
0
votes
2answers
22 views

Why cant this be a Regular Language?

Given L - the language consisting of all the strings of the form $\{0^n 1 ^m\}$ where $m < n$ How can I prove that L is not a regular language?
0
votes
2answers
6 views

Linear search average-case complexity?

I am trying to find the average case complexity of the linear search. I know the answer is O(n), but is this correct: The first element has probability $1/n$ and requires 1 comparison; the second ...
1
vote
1answer
39 views

Are all polynomial-bounded functions computable? [closed]

Let $f = O(g)$, where $g$ is a polynomial. Then is $f$ computable? Let $K(s)$ be Kolmogorov complexity of a string $s$. It's an incomputable function. No. Let $f(x) : \Bbb{Q} \to \Bbb{R}, \ f(x) = ...
1
vote
2answers
53 views

I want to know an estimate of $a_{i, j}$

Let $$ a_{ij} = \begin{cases} -1, & \text{if $i = -1$ and $j = -1$} \\ 1, & \text{if $i = -1$ and $j \ne -1$} \\ 1, & \text{if $i \ne -1$ and $j = -1$} \\ a_{i-1, j-1} + ...
1
vote
3answers
26 views

How do you reckon Big-O analysis with infinite problem sets?

Let $f : X \to Y$ be a problem, for instance, $f: \Bbb{Z} \to $ a factor. Given input measure $n = |x|$, then our problem is $O(g)$ if there exists an algorithm running on a standard machine, and an ...
1
vote
0answers
66 views

Necessary and sufficient conditions for $\rm P \neq NP$ maybe?

Please review the $\rm P \neq NP$ problem here. I'm working on an algebraic approach to this problem, and all my notes are currently here. Conjecture 1 For all $f \in F[x_1, \dots, x_k]$, a minimal ...
0
votes
1answer
15 views

not understanding the part of the answer for drawn turing machine

Could someone please tell me what does capital B mean here ? of course I know R and L stands for right and left... and also I know for example if we have a,b,R (which tells you if you have an a , ...
0
votes
0answers
42 views

My notes on $\Bbb{Z}/p\Bbb{Z}$-theoretic computational complexity

(Question at the very bottom) Def 1. Let $F = \Bbb{Z}_p$ be a finite field. Then an $F^k$-machine is a machine with $k$ input / output memory slots. All computations are done in the field $F$ and ...
0
votes
0answers
14 views

Is the language $L = \{0^m1^n: m \neq n \}$ not context free?

I have been trying to prove that this is not a context free language using the pumping lemma for CFLs. I have tried for hours but am not able to prove it. Is it a context free language or not? How to ...
0
votes
1answer
52 views

Floating Point Number System

I really have no idea of how to do these questions - in fact I have no idea of how to do any question in the paper - but I have tried to figure out what's going on in the course called Computational ...
0
votes
1answer
26 views

how to a draw a turing machine that has the same number of a's ,b's and c's

how to a draw a turing machine that has the same number of a's ,b's and c's SOMELANGUAGE = {abc acb bac bca cab cba aabbcc aabcbc}
0
votes
1answer
20 views

circuits complexity

I ran into this claim and I dont really understand why it is true ( and I need to use it for proving other things) Every function from $(0, 1)^n$ to $(0, 1)$ is computable by a $2^n10n$-sized ...
1
vote
1answer
25 views

The approximation rule implies the equality rule in systems of type assignments

I'm reading Barendregt's Lambda calculi with types (1992). In Proposition 4.1.4.1., he "proves" a lemma which shows the approximation rule implies the equality rule in typed lambda-calculi à la ...
1
vote
3answers
31 views

Which discrete mathematics book to read for a software engineer?

I'm a computer science student, but I lack a good mathematics background. So I decided to start working on that. I was searching in the topic and I found that for computer science a good knowledge of ...
0
votes
0answers
9 views

Computing Object Classification with bayesian statistics

Say I want to know if there is a zebra $\theta$, in an image $x$. According to Bayes statistics applies to image recognition, I should be computing: ...
1
vote
1answer
26 views

Why we take transpose of Vector (Displacement Vector)?

I'm trying to understand some equations that involves transpose of vectors (displacement vectors to be precise) Two set of vectors F and G (with i,j) that corresponds to X,Y value in plane and ...
-1
votes
1answer
25 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
1
vote
0answers
16 views

What about generlizing grammars?

Say we came up with a finite grammar (specifies a finite number of strings) given a set of input strings. How then do we generalize the grammar so that it works for larger input strings and also ...
1
vote
1answer
23 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
0
votes
1answer
20 views

uniqueness of Maximal Independent Set(MIS)

Is maximal independent set of a graph unique? I think between indepent sets, only one of them is maximal. So does it prove that MIS is unique?
0
votes
0answers
45 views

How to simplify following equation?

Here is the equtation: $$\mathrm{P} = \prod_{1\le i \le n}(a_i+1)^2+\left(\sum_{1\le i \le n}a_i\right)\prod_{1\le i \le n}(a_i+1)+\sum_{1\le i \le n}a_i^2-1$$ It is hard to compute each $a_i$, but I ...
0
votes
1answer
49 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
2
votes
0answers
27 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
0
votes
0answers
25 views

Convert nested for loop to mathematical expression

Does anyone know how I can convert this nested for loop into a mathematical expression? ...
0
votes
2answers
42 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
40 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
0
votes
1answer
23 views

create a new formula

I should write a new computer program which includes this computation which I am having trouble with. I may have several cases, ...
0
votes
0answers
10 views

Hierarchy of hardness for the pumping lemma for regular languages.

Whenever I bring up the Pumping lemma for regular languages people often say `better to use the Myhill-Nerode theorem'. I want to make this thought rigorous. Def: A language $L$ is pumpable if there ...
0
votes
0answers
44 views

Todd-Coxeter algorithm: coincidences

I'm trying to understand the Todd-Coxeter algorithm with the help of a multiplication and relator table, but there is one thing about coincidences that is not really clear. For some small groups (for ...
2
votes
4answers
698 views

Convert from base 10 to base 5

I am having a problem converting 727(base 10) to base 5. What is the algorithm to do it? I am getting the same number when doing so: $7*10^2 + 2*10^1+7*10^0 = 727$, nothing changes. Help me figure it ...
1
vote
3answers
31 views

Base 16 to base 10 number conversion

I know that if we want to convert from base 16 to base 10 we do as follows (for example): Given : $15C$ in base $16$ Conversion to base 10: $12 \times 16^0 + 5 \times 16^1 + 1 \times 16^2 = 348$ in ...
0
votes
1answer
83 views

Find all subsets whose sum modulo a value is 0.

How can we find the count of number of subsets of a given set (e.g. {1,7,4,90,23} ) whose sum is a multiple of a given value A. One method which I know of is to store all subset sums modulo A and ...
0
votes
0answers
20 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
0
votes
1answer
24 views

using pumping lemma to prove that a set is not regular

A={s11s|s $\epsilon$ {0}^*} so the strings 00011000 and 000001100000 are accepted of A but not 00100 or 001100000. Demon chooses k. ...
0
votes
2answers
29 views

What can be observed by evaluating a polynomial at roots of order greater than the polynomial itself?

I have been reading through an algorithms book on the use of FFT for large number multiplication. An example it used to emphasize a point was: Evaluate the following polynomial at all roots of unity ...
-1
votes
0answers
41 views

Computer Based Mathematics

I made a post several days ago about the use of computers - and computer programming specifically - in learning mathematics. I have subsequently discovered this project/website by Conrad Wolfram, the ...
0
votes
0answers
13 views

It would be possible to use the covariance matrix $C'=XX^T$ instead of the standard $C=X^TX$ to get the same result on PCA?

It would be possible to use the covariance matrix $C'=XX^T$ instead of the standard $C=X^TX$ to get the same result on PCA? If so, what are the next steps to retrieve the data with reduced ...
1
vote
1answer
28 views

Are there differences between total functions, epimorphic functions and surjective functions?

I've read three definitions which seems to point to the same idea. I've read about epimorphic functions in Mazzola's Comprehensive Mathematics for Computer Scientists - in this book, he treats it as ...
1
vote
4answers
60 views

Examples of partial functions in which the domain is not known?

I was reading this, it mentions about a kind of function in which the exact domain is not known. The only example given is this one - and I'm not really sure I understood it. I got curious about it: ...