Collision problem
id:
collision-problem-232-5362599
title:
Collision problem
text:
The r-to-1 collision problem is an important theoretical problem in complexity theory, quantum computing, and computational mathematics. The collision problem most often refers to the 2-to-1 version: given n even and a function f : { 1 , … , n } → { 1 , … , n } , we are promised that f is either 1-to-1 or 2-to-1. We are only allowed to make queries about the value of f for any i ∈ { 1 , … , n } . The problem then asks how many such queries we need to make to determine with certainty whether f is
brand slug:
wiki
category slug:
encyclopedia
description:
Theoretical problem
original url:
https://en.wikipedia.org/wiki/Collision_problem
date created:
date modified:
2024-01-30T20:12:59Z
main entity:
{"identifier":"Q5147504","url":"https://www.wikidata.org/entity/Q5147504"}
image:
fields total:
13
integrity:
14