What's the deal with Deno? We talk with a major contributor to find out. Listen now.

Questions tagged [proof-techniques]

Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.

Filter by
Sorted by
Tagged with
-1
votes
1answer
122 views

Showing on-line P = NP

I have developed a theorem that proposes a method to build algorithms. All the algorithms produced by this method are in P ... they never go up to more than $6(n^{12})$ operations. Following that, I ...
0
votes
1answer
52 views

Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing

I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, ...
0
votes
0answers
19 views

Comparison tree to get a minimum number of comparisons for merging sorted lists

Suppose A is a sorted list of length n and B is a sorted list of length 2. I am asked to ...
0
votes
1answer
194 views

Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes

I'm having some trouble proving what my title states. Some textbooks refer to almost complete binary trees as complete, so to make myself clear, when I say almost complete binary tree I mean a binary ...
1
vote
3answers
203 views

How can I prove that my greedy algorithm for least guards is optimal?

This is the problem: An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of ...
0
votes
0answers
269 views

Making Candies - HackerRank question - proof of optimality of a greedy approach

I stumbled across this question in HackerRank: Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies. Karl just started a ...
2
votes
2answers
180 views

Induction proofs in Big-O notation

I'm not sure how go about this question: Prove the following inequality. For a correct proof, we require a value of the constant $c>0$ and an $n \in \mathbb N$, such that $\forall n>N : f(x)<...
1
vote
0answers
94 views

Proving a first order logic theorem in equational logic with a term rewriting system

I am trying to translate and prove a theorem, originally written in first order logic (FOL), into a combination of equational logic (EL) and Boolean logic (BL) (more precisely a model of Boolean ...
1
vote
1answer
21 views

Can someone explain me the Credit-Debit proof method for calculating operations?

I've started taking a data structure course and we are currently learning about different data structures. We also learned when to increase the capacity of an array by creating another array with ...
0
votes
0answers
31 views

Proof by padding: $\textsf{TIME}(t_1(n)) = \textsf{TIME}(t_2(n)) \implies \textsf{TIME}(t_1(f(n))) = \textsf{TIME}(t_2(f(n)))$

I've been given the task of proving the statement in the title, which I found out it should be called the translational lemma by means of a padding argument; $f$, $t_1$ and $t_2$ are three ...
0
votes
3answers
138 views

Optimality of a Greedy Algorithm

If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you ...
0
votes
0answers
23 views

How to generate tests using Model-Based Testing paradigm (for a newcomer)

So I just learned of Model-Based Testing. It sounds like this is a practical approach to some level of formal verification of production software applications. As I understand it, you have a ...
4
votes
0answers
71 views

How was the four color theorem proved using brute-force search?

I recently learned some graph theory in Discrete Structures for Computer Science, we learned about the Four Color theorem, I realize there is a mathematical proof for this topic, but how was it ...
1
vote
0answers
19 views

Review of Formal Verification and How to Apply it to Greenfield Project [duplicate]

Last year I looked heavily into Formal Verification, such as automated theorem proving, model checking, type systems, symbolic evaluation, and many others. I probably spent a few weeks or maybe months ...
2
votes
2answers
142 views

What goes into proving two complicated programs are equivalent?

Say I wanted to prove that two programs were equivalent (either rigorously if possible, or informally if not). More specifically, say I have something relatively complex such as an HTTP server ...
1
vote
1answer
43 views

if a graph G(V,E) is connected $|E|\geq|V|-1$

If a graph G(V,E) is connected the number of edges is at least the number of Vertices-1. It is pretty evident if you think about it but how do i prove it formally?
2
votes
1answer
38 views

How to prove properties about a specific modular arithmetic equivalence

Ever since I was introduced to modular arithmetic, I've had some trouble with it. I think it uses a part of my brain that I haven't used often. Anyways, I've been thinking about this specific ...
0
votes
1answer
73 views

Show that a problem is NP-Complete

The problem is, K_longestPath: We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each ...
2
votes
1answer
77 views

Deriving recursive definition from function specification

Given this function specification, where name xs is bound to a list, # denotes its cardinality and ...
-1
votes
2answers
181 views

Uniqueness of solution in Arden's theorem

Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below. My question is: What is the logical reasoning to prove ...
2
votes
0answers
218 views

Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

Given undirected and connected graph $G = (V,E)$. Prove for any DFS run: for any $u,v \in V$ if $u.d>v.d$ then $u.d − v.d ≥ δ(u,v)$ $δ(u,v)$-distance of a shortest path (not necessarily unique) in ...
1
vote
1answer
22 views

Need clarification regarding certificates of coNP problems

NOTE: this is not an attempt to prove $NP \neq coNP$ There is one thing I have never been able to completely digest about the certificates of problems in $coNP$ and I would very much appreciate a ...
0
votes
1answer
72 views

Divide and Conquer a problem into a sub-problem to solve it efficiently

Assume that problem A cannot be solved in O(n^2) time. However, we can transform problem A into a problem B in O(n^2 log n) time, and then solve B, and finally transform the solution of B into the ...
1
vote
1answer
45 views

Is there a proof that “undetectable” malware cannot be written?

In Fred Cohen's paper "Computer Viruses - Theory and Experiments", he proves that for the general case, classifying malware is an undecidable problem. I was wondering whether there might be a ...
0
votes
0answers
50 views

On the complexity of existential and universal quantifiers

I'm trying to analyze the time complexities of the two former kind of quantifiers, I need help figuring out if I'm following the right path or if I'm making mistakes, here's what I've produced so far: ...
1
vote
0answers
76 views

How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?

I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$. $V(j, k) = \begin{cases} tj & k \leq 2 \\...
1
vote
0answers
36 views

Weaker conjectures to prove in order to arrive at P =/= NP

We know we have a long way to go before we come to a proof of P $\neq$ NP. We also know that this road is studded with minor conjectures that will have to be proved/disproved in order to arrive at the ...
2
votes
2answers
1k views

Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]

I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
2
votes
3answers
635 views

Is {a^n: n is a product of exactly two primes} regular?

I am struggling to prove the following question. $L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$ I feel like the language is not regular but I am having trouble proving it. I tried ...
1
vote
1answer
101 views

Codeword constructed by Huffman's algorithm has average length of at most log n

I am interested in the following question: Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords. ...
4
votes
1answer
96 views

Proving with co-induction principles

I'm going through Adam Chlipala's "Certified Programming with Dependent Types" (available here for convenience), and I'm a bit stuck at internalizing the introduction of co-induction principle for the ...
0
votes
0answers
75 views

How to justify $f(n) = O(g(n))$ [duplicate]

The following question is in my homework: Is the statement $f(n) = O(g(n))$ true, when $f(n) = n/2 + 4$ and $g(n) = \sqrt{n} + 2\log_2 n + 3$? I understand how $f(n)$ is the upper bound of $g(n)$. ...
1
vote
0answers
252 views

Proof by reduction and Turing machines [closed]

This is a practice question I have, but I can't wrap my head around it. ............. Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}. B = Blank Position the ...
0
votes
1answer
500 views

How to prove by contradiction that every nonempty hereditary language contains the empty string?

A language L is called hereditary if it has the following property: For every nonempty string x in L, there is a character in x which can be deleted from x to give another string in L. Prove by ...
1
vote
1answer
110 views

The padding argument in the proof of NTIME(n) ⊆ DTIME(n^1.2) implies Σ2-TIME(n^8) ⊆ NTIME(n^9.6)

In "Computational Complexity, A modern approach", Arora & Barak proof the following claim (Claim 5.11.2): Suppose that $\mathsf{NTIME}(n) \subseteq \mathsf{DTIME}(n^{1.2})$. Then $\Sigma_2$-$\...
1
vote
2answers
24 views

Isn't ZKP is a reduction to a hard problem, rather than true zero knowledge?

Take for example "Hamiltonian cycle for a large graph". The proof works by starting with a graph G that contains a hamiltonian cycle, then constructing an isomorphic graph H, and then either showing ...
2
votes
2answers
294 views

Randomly built binary search trees

In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove: The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$. We define "...
2
votes
1answer
204 views

The law of excluded middle and decidability

I will divide my question in two parts. The first part I am sure that there is a objective answer, but I am not sure about the second part. First part: Is it all (decisions) problems trivial to prove ...
1
vote
1answer
127 views

It is decidable whether a pushdown automaton will accept a word? [duplicate]

I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable. I would say that you can simulate a push down automaton with a Turing Machine and, if it ...
8
votes
3answers
3k views

Show that there are infinitely more problems than we will ever be able to compute

I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
2
votes
2answers
96 views

Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
-3
votes
1answer
103 views

Could we define the decimal notation of a natural number as a series of operations applied to 0? [closed]

People have made mistakes. For that reason, there probably is a demand by some people for a computer program that's easier to verify makes the calculations properly. I think that according to the ...
1
vote
1answer
74 views

How to prove $L \notin \texttt{DSPACE}(f)$

I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to ...
3
votes
1answer
76 views

How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?

For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$. I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I ...
0
votes
0answers
43 views

Proof that this sorting algorithm sorts the input [duplicate]

I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $n$, sort(A,0,n-1) will sort it. ...
2
votes
0answers
115 views

Red-black tree trinode restructuring after insertion and deletion

When performing an insertion/deletion on a red-black tree, how can be argued or proved that it requires at most one/two trinode restructuring(s) respectively? My thoughts so far were: after inserting ...
2
votes
1answer
66 views

How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?

Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each ...
1
vote
1answer
70 views

How to correctly describe this action, deleting an edge that “shortcut” some vertices

Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below: 1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
0
votes
0answers
85 views

proving DFA stuck

This DFA fulfills: Define a function $diff: \{0,1\}^*\to\Bbb Z$, for $w \in\{0,1\}^*$, $diff(w)=($# of 1's in $w)- ($# of 0's in $w$). Thus, $diff(\epsilon)=0$; $diff(0)=−1$; $diff(1)=1$. Let $L = ...
0
votes
0answers
35 views

dfa subtract multiple of 3 [duplicate]

Define a function 𝑑𝑖𝑓𝑓 ∈{0,1}→ℤ so: for everything w ∈{0,1}, diff w = # of 1's in w- # of 0's in w. Thus: 𝑑𝑖𝑓𝑓 𝜀=0; 𝑑𝑖𝑓𝑓 0=−1; 𝑑𝑖𝑓𝑓 0=−1; Let 𝐿 = {𝑤∈ {0,1} * | 𝑑𝑖𝑓𝑓 𝑤 = 3𝑚 ...

1
2
3 4 5
12