AncomWiki

Composite rule: 해시 검증의 한계와 조합 폭발 문제

Properties1
description해시 기반 검증 방식은 문장에 여러 조합이 공존할 경우 충돌하여 실패하는 치명적 약점을 가진다. 이를 해결하기 위해 atomic class의 부분집합을 모두 생성해 검증하는 방식은 조합의 수(2^n - 1)로 인해 시간 복잡도가 급증하여 비효율적이다.

37 min read

Composite rule: 해시 검증의 한계와 조합 폭발 문제

Source

  • Field Notes/ReturnZero/Daily Notes/Day 454.. 2022-09-27.md

Summary

해시 기반 검증 방식은 문장에 여러 조합이 공존할 경우 충돌하여 실패하는 치명적 약점을 가진다. 이를 해결하기 위해 atomic class의 부분집합을 모두 생성해 검증하는 방식은 조합의 수(2^n - 1)로 인해 시간 복잡도가 급증하여 비효율적이다.

Key Points

  • 해시 검증은 단일 조합 존재를 전제로 하므로, 다중 조합 환경에서 오류 발생
  • 부분집합 기반 브루트포스 검증은 지수적 시간 복잡도(2^n - 1)로 인해 실용성 부족
  • 다중 조합 처리를 위한 대안적 접근 필요 (원문 미완성)

그래프 뷰

백링크