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.
701
questions
2
votes
1
answer
38
views
Proof for Gas Refills on Circular Route Problem
The circular route gas station problem asks: If given a car with an unlimited gas tank, find the gas station on a circular road that if started from would allow you to travel station to station ...
- 23
2
votes
1
answer
33
views
A decision tree proof for the lower bounds worst case of an algorithm that k-nearly sorts an Array
Let says you want to k-sort an array A with a comparison based algorithm.
To be k-sorted, each individual item in the array A can be at most k positions away from it's actual correct position when ...
- 21
0
votes
1
answer
47
views
How would I prove implications of this structure?
Consider the following to prove: $(A \implies B) \implies (C \implies D)$
Could this be proved by assuming A then proving B, then using A and B to prove C, then using A, B and C to prove D? or would ...
- 173
1
vote
1
answer
40
views
Proving $f(n) = 1 + c + c^2 + \cdots + c^n = \Theta(1) $
How can I prove that the function $$ f(n) = 1 + c + c^2 + \cdots + c^n $$ is $\Theta(1)$ when $c<1$?
where $n \in \mathbb{N}$ and $c \in \mathbb{R}$, with $c>0$. Can I use limits?
Thank you in ...
- 11
2
votes
3
answers
51
views
Prove that the L1 distance between two arrays is minimized when both are sorted
Suppose you are given two arrays of the same length $n$, say $a$ and $b$ containing unique positive integers. The L1 distance between $a$ and $b$ is defined as:
$$d_1(a, b) = \sum_{i = 1}^n \lvert a_i ...
- 83
1
vote
0
answers
29
views
Minimum expected number of path to cut graph problem
I came up with a problem but was unable to show the hardness of the problem (NP/#P/P-hard). The problem is as follows. Given a directed graph $G=(V, E)$, each edge will have a confidence score $c$. ...
- 11
-1
votes
1
answer
28
views
Show that it is Np-hard to determine whether a given graph has the crossing number k
I want to prove that this problem to find whether the crossing number of any given graph is K or not, is NP-Hard. I don't know how to do this. Can someone help me with this ?
- 1
1
vote
2
answers
43
views
Intuitive explanation/overview of non-looping non-termination proofs
Looping non-termination is intuitively easy to understand and demonstrate, by finding/showing a sequence of transformations that cycles back itself. Say, using the rewriting system:
...
- 191
0
votes
0
answers
7
views
Load Balancing with No Overlap
Problem
Suppose there are $n$ jobs $J_1, \ldots, J_n$ that need to be completed using $m$ machines $M_1, \ldots, M_m$. Each job $J_i$ consists of a set $S\left(J_i\right)$ of $k_i$ sub-chores $s_1, \...
- 127
1
vote
1
answer
53
views
Prove maximum score is achieved by being greedy
I have a list of tokens T, of length n. Initially I have power p and a ...
- 284
-3
votes
3
answers
62
views
Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$
Anyone please answer the question:
Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$.
- 15
-1
votes
1
answer
54
views
Proving tight bound Θ for worst-case running time of an algorithm without proving lower bound Ω
See this answer first: Proving worst-case running time is in $\Omega(n^2)$
Understanding the linked answer for insertion sort leads to the following statement. Prove that the statement is either ...
- 13
2
votes
2
answers
97
views
can we computably list every primitive recursive function?
i have seen some articles where they use the diagonalization argument to prove the existence of non-primitive recursive functions. But this should only work if we can create an infinite list of every ...
3
votes
1
answer
47
views
Invariance Textbook Problem: Clarification Needed
I am currently reading Michael Soltys' Analysis of Algorithms (2nd Edition), and Problem 1.13 of the subsection titled Invariance reads:
Let $n$ be an odd number, and suppose that we have the set $\{...
0
votes
0
answers
56
views
The formal proof that one Turing Machine computes one specific function
I have asked one similar question QA_1 "The formal proof that one Turing Machine recognizes one specific language" and the answer fills the part "It does not generate any string that is ...
- 203